Nearest Element - MarisaOJ: Marisa Online Judge

Given an array

$A$ of

$n$ positive integers. The distance between two elements

$i$ and

$j$ is defined as

$|i - j|$ . For each element

$i$ in the array, find the element

$j$ closest to

$i$ such that

$\text{gcd}(A_i, A_j) \neq 1$ . ### Input - The first line contains an integer

$n$ . - The second line contains

$n$ integers

$A_i$ . ### Output - Print

$n$ integers, where the

$i$ -th integer represents the position of the element closest to

$i$ satisfying the condition. If no such element exists, print

$-1$ . If there are two satisfying indices, print the smaller index. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le A_i \le 10^6$ . ### Example Input:

$5 2 3 4 9 17$

Output:

$3 4 1 2 -1$

Topic

Math

Binary search

Rating

1200

Source

HackerEarth

Solution (1)

Solution