In some close russian circles this task was born. Can you solve it?
You have an array of length N of non-negative integers. Also you have to answer Q queries.
Query (L, R) — you have to find a max[ lcm(A, B) — gcd(A, B) ], where A and B — some elements of segment (L, R) (not necessarily of different index). Consider gcd(0, 0) = 0, lcm(0, 0) = 0.
N <= 10^5, Q <= 10^5
Write your ideas in comments.
Full text and comments »