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≤105
1≤A[i]≤104
SCORING
For 40% of the scores- 1≤N≤103
For 60% of the scores- 1≤N≤105
First element is the left extreme thus we output -1 for it.
4 has GCD 2 with 2 on index 1
6 has GCD 2 with 4 on index 2
7 has GCD 1 with 6 on index 3,although 7 has gcd 1 with all integers on left but 6 is closest so we output 3
9 has GCD 3 with 6 on index 3
