407875: GYM102911 K Kallipolis

What makes a good leader?

Bob reflected on that topic as he read Plato's Republic and Marcus Aurelius' Meditations. Plato believed in the ideal philosopher king, a ruler "who possesses both a love of wisdom, as well as intelligence, reliability, and a willingness to live a simple life". He goes on to further posit that for a utopia to be achieved, either the philosophers must become kings, or the kings must adequately and genuinely philosophize.

Bob then imagines the following (admittedly unrelated) thought experiment. Suppose we have $$$N$$$ philosophers, indexed $$$1$$$ to $$$N$$$, and whose leadership values are integers $$$A_1, A_2, \dots A_N$$$. We say that philosopher $$$i$$$ dominates philosopher $$$j$$$ if $$$A_i$$$ is divisible by $$$A_j$$$. Then, Bob decides that the philosopher king must be the philosopher who dominates all the other philosophers. If there are multiple possible philosopher kings, Bob chooses the one with the smallest index.

Given the leadership values of the philosophers, can you help Bob identify if any of them are fit to be philosopher king? If yes, identify who it should be.

Recall that we define an integer $$$a$$$ to be divisible by another integer $$$b$$$ if there exists some integer $$$k$$$ such that $$$a = kb$$$.

The first line of input contains a single integer $$$N$$$, the number of philosophers.

The second line of input contains $$$N$$$ space-separated integers, the leadership values $$$A_1, A_2, \dots, A_N$$$.

If there exists a philosopher king, output their index. Otherwise, output $$$-1$$$ to indicate that there is no philosopher king.

$$$1 \le A_i \le 10^9$$$

Subtask 1 (50 points):

$$$1 \le N \le 5$$$

Subtask 2 (20 points):

$$$1 \le N \le 1000$$$

Subtask 3 (30 points):

$$$1 \le N \le 2\cdot 10^5$$$

4
1 215 43 5

2

4
201 202 227 228

-1

5
224 224 224 224 224

1

In the first sample, we see that $$$215$$$ is divisible by $$$5$$$, $$$43$$$, and $$$1$$$, so philosopher $$$2$$$ is king.

In the second sample, we can show that none of the philosophers fit the criteria for king.

In the third sample, any of the philosophers satisfy the conditions, so we choose the one with smallest index, which is $$$1$$$.