Fedor plays in a band, consisting of n musicians. They are all fans of The Beatles band. They want to repeat famous photo of musicians made on Abbey Road long time ago. Fedor and his friends found a good place to take photo and lined up along the beginning of a pedestrian crossing. They will start walking simultaneously, making several steps, and i-th person makes a single step in $a_i$ seconds.

They agreed, that the photo has to be taken the first time, when they all finish their step simultaneously.

But Fedor likes to be special. He spoke to the photographer and told him to take photo at the first moment, when $n-1$ of the guys finish their steps and one of them doesn't.

Find, which one of the guys doesn't finish his step, when the photo is taken.

Input format

First line contains single integer n — the number of musicians in the band ($2 \le n \le 5 \cdot 10^5$).

Second line consists of n integers $a_1, a_2, \ldots a_n$ — time for a single step of each person ($1 \le a_i \le 10^6$).

Output format

Output single integer: musician number, who doesn't finish his step, when the photo is taken. If no photo is going to be taken, output -1.