Integers have friends interval GCD + double pointer

subject link

Ideas

For two adjacent numbers a b
Interval module $p$ congruence $a\%p=k1\ast x+c,b\%p=k2\ast x+c$ Introduction $(a-b)\%p=k\ast x$
Consider the differential array , If there is an interval in the difference array $[l,r],gcd>1$ . In the original array interval $[l-1,r]$ Modulo identical number $x$ congruence
Maintenance interval $gcd$ Sure Segment tree and can be maintained dynamically
There is no need to modify $ST$ Tables can also maintain intervals $gcd$
How to enumerate the answers ？
Violent enumeration is not desirable , Because of the interval $gcd$ Monotonicity , It can be divided into two parts It's fine too
Enumerate right endpoints $r$, Then move the left endpoint $l$

Code

#define int long long
#define endl "\n"
#define _orz ios::sync_with_stdio(false),cin.tie(0)
#define mem(str,num) memset(str,num,sizeof(str))
#define forr(i,a,b) for(int i = a; i <= b;i++)
#define forn(i,n) for(int i = 0; i < n; i++)
#define dbg() cout <<"0k!"<< endl;
typedef long long ll;
int pri[16] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
const int inf = 0x3f3f3f3f;
const int INF = ~0ULL;
const int N = 1e6+10;
int a[200005],b[200005];

// struct node{
    
// int l,r;
// int dat;
// #define ls i<<1
// #define rs i<<1|1
// }t[200005<<2];

// void build(int i,int l,int r){
    
// t[i].l = l,t[i].r = r;
// if(l==r){
    
// t[i].dat = b[l];
// return;
// }
// int mid = (l+r) >> 1;
// build(ls,l,mid);
// build(rs,mid+1,r);
// t[i].dat = __gcd(t[ls].dat,t[rs].dat);
// }

// int ask(int i,int l,int r){
    
// if(l <= t[i].l && r >= t[i].r){
    
// return t[i].dat;
// }
// int res = 0;
// int mid = (t[i].l+t[i].r)>>1;
// if(l <= mid) res = __gcd(res,ask(ls,l,r));
// if(r >mid ) res = __gcd(res,ask(rs,l,r)); 
// return abs(res);
// }


int f[200005][21];
int n;
void ST(){
    
    //  No initialization 
    forr(i,1,n) f[i][0] = b[i];
    forr(i,1,20)for(int j = 1;j+(1<<i)-1 <= n;j++){
    
        f[j][i] = __gcd(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    }
}

void solve(){
    
    cin>>n;
    forr(i,1,n) cin>> a[i],b[i] = abs(a[i]-a[i-1]);
    ST();
    if(n==1){
    
        cout << 1 << endl;
        return;
    }
    //build(1,1,n);
    int l = 2; //  Minutiae   Because the differential array b[1] Same as the original array   So we have to go from l=2 Start enumeration , Because sometimes b[1] It may lead to answers within the range of answers provided +1, Examples 2
    int res = 1;
    for(int r = 2;r <= n;r++){
    
        if(b[r]==1) continue;
        while(l < r){
    
            int len =__lg(r-l+1);
            if(__gcd(f[r-(1<<len)+1][len],f[l][len]) == 1) l++;
            else break;
        }
        res = max(res,r-l+2);
    }
    cout << res << endl;
}


signed main()
{
    
    _orz;
    int t;cin>>t;
    while(t--) solve();
    return 0;
}