You can use a DP-like idea. The intuition for me was, for a point, the closest point to [x, y] must either have the same x value (so it's on the same vertical line), or it must be on a path through [x — 1, y] or [x + 1, y].

Try writing the inequality that needs to be satisfied based on the pair you pick.

Here is a correct submission that uses the idea above: https://codeforces.me/contest/1632/submission/144586184

I think the key observation is that given a[i], there can be at most around log2(a[i]) distinct gcds among gcd(a[i]), gcd(a[i — 1], a[i]), ..., gcd(a[0], ..., a[i]).

So, combined with the monotonic observation, it's fine to maintain a partitioning of [0, i] into intervals, one for each distinct gcd. So in log2(i) time you can find the earliest position j such that gcd(a[j], ..., a[i]) is equal to its length. I guess you could also binary search but that's unnecessary.