给一个很快的 $O(n)$ 做法

最开始比较容易想到：对于每个数，找到数左边和右边第一个它不能整除的数，就能确定区间的范围

于是有人就会容易地想到：可以用 $二分$ 。可是这样还不够优秀

于是不容易地想到：可以用 $类似单调栈$ 实现

这个单调栈里面的数需满足：相邻两个数之间呈倍数关系。入栈的时候若不满足，就弹出栈顶，直到满足。

因此，一个数被谁弹出栈，它右侧第一个它不能整除的数就是谁

正着反着跑两遍即可。

150ms，跑得飞快

#include<iostream>
#include<cstdio>

using namespace std;

inline int Rd(){
	int x=0,f=1, c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
} 

int n,a[300005];
int st[300005],top, rm[300005],lm[300005];
int maxx,ans[300005],tot;

int main(){
//	freopen("interval.in","r",stdin);
	n=Rd();
	for (int i=1;i<=n;i++){
		a[i]=Rd();
	}
	for (int i=1;i<=n;i++){
		while (top && (a[st[top]]>a[i] || a[i]%a[st[top]]!=0)) rm[st[top--]]=i;
		st[++top]=i;
	}while (top) rm[st[top--]]=n+1;
	
	for (int i=n;i>=1;i--){
		while (top && (a[st[top]]>a[i] || (a[i]%a[st[top]])!=0)) lm[st[top--]]=i;
		st[++top]=i;
	}while (top) lm[st[top--]]=0;
//	for (int i=1;i<=n;i++){
//		cerr<<lm[i]<<" "<<rm[i]<<endl;
//	}cerr<<endl;
	
	for (int i	=1;i<=n;i++){
		int tmp=rm[i]-lm[i]-1;
		if (maxx<tmp){
			maxx=tmp;
			ans[tot=1]=lm[i]+1;
		}else if (maxx==tmp){
			if (ans[tot]!=lm[i]+1){
				ans[++tot]=lm[i]+1;
			}
		}
	}
	printf("%d %d\n",tot,maxx);
	for (int i=1;i<=tot;i++){
		printf("%d ",ans[i]);
	}
	printf("\n");
	return 0;
}