Short Statement Here

Prerequsite: Inclusion exclusion/mobius function, seive, stack

Let's try to solve this problem using stack. Sort the array in non increasing order. Idea is, we'll run a loop from 1 to n and keep including current element on the top of our stack. Before including it to the stack we do some operation. Let's say elements of our stack is as follows: (from top to bottom)

s1 s2 s3 s4 s5 .......... (s1<=s2<=s3<= ......... our array is sorted in non increasing order . So this condition will be true.)

Let's say our current element is a_i and s3 is coprime to a_i. Then s1, s2 can't produce a better answer. Let's see an example. If elements of our stack is 8 12 13 16 and our current element is 4 then 8 and 12 cant produce better answer than 4 * 13. So we can remove them from stack and we don't have to worry about them anymore.

Our solution is to for every ai we pop the top element from the stack as long as we have integers in the stack which are coprime to a_i. Then push a_i to the stack. So, next challenge is to know if there is a coprime number to a_i in the stack. If there is, then how many. It can be done using inclusion exclusion/ mobius function.

We need to precalculate divisors of every integer from 1 to 10^6 using idea of seive and vector array. We also need a counter array. When we push a_i in the stack we increase count of all it's divisor by 1. When we pop a_i from stack we will decrease count of all it's divisors by 1. Let's a_i=p1^x1 * p2^x2 * p3^x3 where p_i are primes and x_i are their power. So count of stack elements which are coprime to a_i = Size of stack - count(p1) - count(p2) -count(p3) + count(p1 * p2) +count(p1 * p3) + count(p2 * p3) -count(p1 * p2 * p3). In another word ∑count((d_i)) * mobius(d_i) where d_i is divisor of ai.
If f(a_i) is number of divisors of ai then complexity is O(∑f(a_i)) . If you work with only unique numbers then complexity will be O(n ln n).

Harder version: https://codeforces.com/contest/1285/problem/F