Description：

给出一个长度为 $N$ 的序列 $A[1]...A[N]$ ，定义一个合法区间 $ [L,R]$ 当且仅当区间 $GCD$ 在这个区间内，求最长合法区间长度。

$1\leqslant n \leqslant 4\times10^6$

Solution：

假设以这个数为 $GCD$ 的区间为 $[L,R]$ ，那么 $[L,R]$ 内除这个位置都不会成为最后的答案，因为他们一定都是 $GCD$ 的整数倍，他们能扩展到的 $GCD$ 也能扩展到，但又不能简单将他们删除，因为可能区间内有多个相同的数，于是把这些数的有边界都设成 $GCD$ 能扩展的最右边界，正反各做一次统计一下即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 4000010

long long a[MAXN];

inline long long read()

{

	register long long res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int rig[MAXN];

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)a[i] = read();

	register int cur = 1;

	for(register int i = 1;i <= n;)

	{

		while(cur < n && a[cur + 1] % a[i] == 0)++cur;

		for(;i <= cur;++i)rig[i] = cur;

	}

	cur = n;

	register int ans = 0;

	for(register int i = n;i >= 1;)

	{

		while(cur > 1 && a[cur - 1] % a[i] == 0)--cur;

		ans = max(ans,rig[i] - cur + 1);

		i = cur - 1;

	}

	printf("%d\n",ans);

	return 0;

}