铁路

小S有一个长度为\(n\)的序列。

一个区间\([L,R]\)是好的，当且仅当存在\(k\in[L,R]\)，使得对于任意的\(i\in[L,R]\),\(a_k|a_i\)。

现在，小S想要知道，最长的好的区间是多少，并且这些区间是什么。

输入格式
第一行一个整数\(n\)。

接下来一行\(n\)个数，第\(i\)个表示\(a_i\)。

输出格式
第一行两个数，\(m\)和\(len\)分别表示最长的好区间个数以及这些区间的\(R?L\)。

接下来一行\(m\)个数，按升序输出每个最长的好区间的左端点。

样例
样例一
input

5
4 6 9 3 6

output

1 3
2

样例二
input

5
2 3 5 7 11

output

5 0
1 2 3 4 5

约定与限制
对于\(30\%\) 的数据，满足 \(n\le30,1\le a_i\le32\)。

对于\(60\%\) 的数据，满足 \(n\le3000,1\le a_i\le1024\)。

对于\(80\%\) 的数据，满足 \(n\le300000,1\le a_i\le1048576\)。

对于\(100\%\) 的数据 ，满足 \(1\le n\le5×10^5,1\le a_i<2^{31}\) 。

时间限制:\(1s\)

空间限制:\(512MB\)

这题好像连暴力都有点难打。我们先看一下怎么暴力。
一种可行的方法就是枚举开头和结尾，然后暴力判断。这是一个很稳定的\(O(n^3logn)\).能稳过\(30\%\)的数据点。
还有另外一种暴力。枚举这个成为\(a_k\)的数，然后向左右扩展，如果这个数可以被\(a_k\)整除，那么就把这个区间扩大一个数。这个算法是\(O(n^2logn)\)的。

我们扩展的时候很明显可以用二分，二分左右扩展的端点，如果这一段区间的最大公因数数是\(a_k\)的倍数，那么就扩大范围。问题来了，怎么判断一段区间的最大公因数是不是\(a_k\)的倍数呢？

线段树可以，但\(O(nlog^3n)\)的复杂度还是无法接受。gcd可以用ST表维护，预处理复杂度\(O(n(logn+logw))\),当中w是值域。但是查询时还有一个\(log\)呢。我们只需要直到gcd可不可以被\(a_k\)整除就行了，所以将两个区间看一下可不可以整除就行了。

#include
#include

然而这题还有一个更为简单的做法。
还是考虑枚举成为区间gcd的数，然后考虑暴力扩展，尝试在扩展时加优化。
首先设往左右扩展出\((l,r)\)这个区间，那么区间里别的数再扩展出来的区间也被这个区间所包含。所以直接将i赋值为r+1.
往右扩展可以保证是\(O(n)\)的，那么我们考虑如何优化往左扩展。如果在扩展时出现一个和中心数一样的数，那么这个区间已经被扩展过了，就不用再扩展了。
当然，还是要尝试证明复杂度。
往左扩展时，每个数字只会被他的每一个因数扩展一次。他的因数个数为\(\sqrt{n}\),所以复杂度貌似为\((n\sqrt{n})\)
但是，能同时向左扩展到一个数的数，一定是递减且成倍数关系，不然最远的那一个扩展不过来，所以复杂度为\(O(nlogn)\),而且常数比方法一小很多。

#include
const int N=5e5+5;
int n,a[N],l,r,ret,ans[N],idx;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<=n;i++)
	{
		for(l=i-1;l&&a[l]%a[i]==0&&a[l]!=a[i];l--);
		for(r=i+1;r<=n&&a[r]%a[i]==0;r++);
		l++,r--,i=r;
		if(r-l>ret)
			ret=r-l,ans[idx=1]=l;
		else if(r-l==ret) 
			ans[++idx]=l;
	}
	printf("%d %d\n",idx,ret);
	for(int i=1;i<=idx;i++)
		printf("%d ",ans[i]);
	return 0;
}