Cerința

Într-o zi, câțiva copii plictisiți de “Popa Prostul”, au inventat jocul “Popa Prostul 2”. Acest joc se joacă cu mai multe cartonașe identice. La început, fiecare jucător primește un număr de cartonașe. Primul jucător pune pe masă un număr de cartonașe egal cu cel mai mare divizor al numărului de cartonașe pe care îl avea în mână. Următorul pune un număr maxim de cartonașe, divizor al numărului de cartonașe pe care le are în mână, dar și divizor al numărului de cartonașe pus de jucătorul dinainte. Jocul continuă până când unul dintre copii pune jos un singur cartonaș. Jucătorul care va fi nevoit să pună un singur cartonaș va fi pierzătorul.

Dându-se numărul n de copii și numărul de cartonașe pe care îl primește fiecare, să se determine numărul de ordine al copilului care va pierde jocul.

Date de intrare

Pe prima linie a fișierului de intrare cartonase1.in se va găsi numărul n de copii. Pe a doua linie vor fi n numere: \( {x}_{1},{x}_{2}…{x}_{n} \) reprezentând numărul de cartonașe pe care îl primește fiecare jucător.

Date de ieșire

Pe prima linie a fișierului cartonase1.out se va scrie numărul de ordine al pierzătorului sau valoarea -1 dacă nu există pierzător.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 1 ≤ xi ≤ 100.000.000
• Primul jucător va avea numărul de ordine 1.

Exemplu:

cartonase1.in

8
30 15 6 18 303 45 44 25

cartonase1.out

7

Explicație

Primul jucător va pune 30 de cartonaşe.
Al doilea jucător va pune 15 cartonaşe.
Al treilea jucător va pune 3 cartonaşe.
Jucătorii 4, 5 şi 6 vor pune 3 cartonaşe fiecare.
Jucătorul cu numărul 7 va fi obligat să pună 1 cartonaş şi va pierde jocul.