Processing math: 100%
Nearest Element - MarisaOJ: Marisa Online Judge

Nearest Element

Time limit: 1000 ms
Memory limit: 256 MB
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 gcd(Ai,Aj)≠1. ### Input - The first line contains an integer n. - The second line contains n integers Ai. ### 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≤n≤105. - 1≤Ai≤106. ### Example Input: 5234917 Output: 3412-1