Suppose we are given an Array A of size N (N<=100000) and each element of array A[i]<=100000. Now I want to find rightmost element A[j] in subarray A[1]....A[i-1] for each A[i] such that gcd(A[j],A[i]) is 1 i.e. both are relatively comprime. How can this be done efficiently?