Algorithm:

For indices $$$L$$$ and $$$R$$$, do the following:

• Recursively find the answer for indices $$$L$$$ to $$$mid$$$ and $$$(mid+1)$$$ to $$$R$$$
• Iterate from $$$i=mid, ..., L$$$ and store a map of unique GCD values to indices $$$(map_L[GCD(A_i,...A_{mid})] = i)$$$
• Do the same for right half i.e. $$$(map_R[GCD(A_{mid+1},...A_j)] = j)$$$
• Do a complete comparison between every pair of elements in these two maps:
  For $$$(x,i)$$$ in $$$map_L$$$ and $$$(y,j)$$$ in $$$map_R$$$, if $$$GCD(x,y)>1$$$ then $$$ans = max(ans, j-i+1)$$$

Analysis:

Here, time complexity for the merge step alone would be $$$O(n\log10^{18})$$$ for the GCDs $$$+$$$ $$$O(|map_L|\cdot|map_R|)$$$ for the comparison step. But $$$|map|\leq\log(10^{18})<60$$$ so overall the merge step takes $$$O(n\log10^{18})$$$ time.

Complete algorithm would thus take $$$T(n)=O(n\log n\log10^{18})$$$ time as given by the recurrence relation — $$$T(n) = 2T(n/2) + O(n\log10^{18})$$$

#include <bits/stdc++.h>
using namespace std;
#define forn(i,x,n) for(int i = x; i < n; ++i)
typedef long long ll;

vector<ll> a;

ll gcd(ll a, ll b) {
    return b? gcd(b, a%b): a;
}

int calc(int l, int r){

    if(l == r)
        return a[l] != 1;

    int mid = (l+r)/2, ans = max(calc(l, mid), calc(mid + 1, r));

    ll gc = 0, i = mid;
    unordered_map<ll,int> ml, mr;

    while(i >= l){
        gc = gcd(gc, a[i]);
        if(gc > 1)
            ml[gc] = i;
        else
            break;
        i--;
    }

    gc = 0, i = mid + 1;

    while(i <= r){
        gc = gcd(gc, a[i]);
        if(gc > 1)
            mr[gc] = i;
        else
            break;
        i++;
    }

    for(auto [y, i]: mr)
        for(auto [x, j]: ml)
            if(gcd(y, x) > 1 && ans < i - j + 1)
                ans = i - j + 1;

    ml.clear(), mr.clear();

    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, t;
    cin >> t;

    while(t--){
        cin >> n;
        a.assign(n,0);
        forn(i,0,n)
            cin >> a[i];
        n--;
        forn(i,0,n)
            a[i] = abs(a[i] - a[i + 1]);

        cout << calc(0, n - 1) + 1 << '\n';
    }
    return 0;
}