В очень узких кругах возникла интересная (нет) таска на запросы. Сможете ли вы ее решить?

Дан массив размера n из целых неотрицательных чисел. Дано q запросов одного вида.

Запрос на подотрезке (L, R) — нужно вывести max[ lcm(a, b) — gcd(a, b) ], где a и b — какие-то числа на подотрезке с L по R. Cчитать что gcd(0, 0) == 0 и lcm(0, 0) = 0.

n <= 10^5, q <= 10^5

Напишите свои идеи в комментариях.