重现赛链接： https://fjnuacm.top/contest/693675eadfc2a2a864eec8fb

隔了大半年来补低程题的 $🐖$ 来了......$\\[20pt]$

首先观察题干，我们可以知道：

一个优秀的小组，实际就是数组中的一个区间，满足区间内所有数的最小公倍数 $＞$ 区间最大值。

即如果区间 $[l,r]$ 满足：

$$0 \le l \le r < n$$ $$\operatorname{max}_{i=l}^{r} a_i < \operatorname{lcm}_{i=l}^{r} a_i$$

则称区间 $[l,r]$ 是优秀的。$\\[20pt]$

显而易见的，对于一个不优秀的区间，一定有 区间最大值=区间最小公倍数 ，因此我们可以令其最大值和最小公倍数均为 ${d}$ 。

如果该区间的某一个子区间是优秀的，那么该子区间内一定不含 $d$ ，因为如果含 $d$ ，则一定会有 最小公倍数=最大值=d ，因此我们可以 利用区间最大值分割不优秀区间 ，以找到它的优秀子区间。

考虑如下操作：

$\quad$维护一个 $ma$ 表示记录的最大值。

$\quad$从区间 $[0,n-1]$ 开始进行如下递归：

$\qquad$检查区间长度是否超过 $ma$ ，如果不超过，直接 $return$ 。

$\qquad$检查区间是否优秀:

$\qquad \quad$如果优秀，更新 $ma$ 为区间长度，然后 $return$ 。

$\qquad \quad$如果不优秀，找到区间内所有的最大值，利用最大值将区间分割为多个子区间，继续递归检查这些子区间。

$\quad$最后输出 $ma$ 即可。$\\[20pt]$

时间复杂度 $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
#define int long long

int Max=1e9+1;
int ma=0;

int gcd(int a,int b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}

void Try(vector<int> &a,int l,int r)
{
    if(r-l+1<=ma)return;
    int lcm=a[l];
    int m=a[l];
    for(int i=l+1;i<=r;i++)
    {
        m=max(m,a[i]);
        int g=gcd(lcm,a[i]);
        lcm=min(Max,lcm/g*a[i]);
    }
    if(m!=lcm)
    {
        ma=r-l+1;
        return;
    }
    vector<int> s;
    s.push_back(l-1);
    for(int i=l;i<=r;i++)
    {
        if(a[i]==m)s.push_back(i);
    }
    s.push_back(r+1);
    int t=s.size();
    for(int i=1;i<t;i++)
    {
        Try(a,s[i-1]+1,s[i]-1);
    }
}

void solve()
{
    ma=0;
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto &i:a)
    {
        cin>>i;
    }
    Try(a,0,n-1);
    cout<<ma<<"\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}