Sheldon is a genius and today he has got an array under his interest.
He wants to find ,for all elements of the array, the nearest element on the left such that GCD of both the elements is maximum. (See sample test case for explanation.)
Note: For first element, output will always be -1.
INPUT
First line contains an integer N - size of the array.
Second line contains N space separated integers describing the array
OUTPUT
Output the index of the nearest element required in the problem.
CONSTRAINTS
\(1 ≤ N ≤ 10^{5} \)
\(1 ≤ A[i] ≤ 10^{4} \)
SCORING
For 40% of the scores- \(1 ≤ N ≤ 10^{3} \)
For 60% of the scores- \(1 ≤ N ≤ 10^{5} \)