Today I created this problem, idk maybe it exists somewhere

We have array of n numbers n <= 2e4, a[i] <= 1e6 And we have q queries q <= 2e4, 1 <= l <= r <= n

Initially we have subset with element a[l:r], we need to erase minimal number of elements from this subset so that gcd(subset) > 1 gcd of subset becomes bigger than 1

**I have some idea but idk if it’s right**

Did I understand right, you find gcd like, gcd(a[l], a[l + 1], a[l + 2] ... a[r])?

Oh sorry, I edited the blog, i had a mistake At first we take elements a[l] ... a[r] as one set and we need to erase minimum number of element in this set to have gcd > 1

For example if set is

6 15 8 10

we need to erase 15 then gcd becomes 2

Your idea is correct.

Thanks, but I can’t find maximum out of same numbers in range fast

Since 8*n is ~10^5, just apply mo's algorithm.