显然若右端点确定，gcd最多变化log次。容易想到对每一种gcd二分找最远端点，但这样就变成log^3了。注意到右端点右移时，只会造成一些gcd区间的合并，原本gcd相同的区间不可能分裂。由于区间只有log个，暴力即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 100010#define ll long longll read(){ ll x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,r[N],tmp[N],head=1,tail;ll a[N],ans,g[N];ll gcd(ll n,ll m){ return m==0?n:gcd(m,n%m);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4488.in","r",stdin); freopen("bzoj4488.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) { r[++tail]=i;g[tail]=a[i]; for (int j=head;j
           
            =head;j--) { int t=j; while (t>head&&g[t-1]==g[j]) t--; x--,r[x]=r[t],g[x]=g[t]; j=t; } head=x; for (int j=head;j<=tail;j++) ans=max(ans,(i-r[j]+1)*g[j]); } cout<