The Beatles
Tag(s):

LCM, Math, Medium-Hard, Prime Factorization

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5
5 12 10 3 15

SAMPLE OUTPUT
2

Explanation

The first moment when all except one of the musicians finish a step is at time 30. First, third, fourth and fifth musicians finish their step, but second doesn't. Because 30 is divisible by 5, 10, 3 and 15, but is not a multiple of 12.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

November Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Basic Math
• Math > Combinatorics
• Algorithms > Graphs
• Algorithms > Dynamic Programming