CodeForces - 359D

Simon has an array a₁, a₂, ..., a_n, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

there is integer j (l ≤ j ≤ r), such that all integers a_l, a_l + 1, ..., a_r are divisible by a_j; value r - l takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input

The first line contains integer n (1 ≤ n ≤ 3·10⁵).

The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).

Output

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.

Example Input 5 4 6 9 3 6 Output 1 3 2 Input 5 1 3 5 7 9 Output 1 4 1 Input 5 2 3 5 7 11 Output 5 0 1 2 3 4 5 Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

我们要是直接去找左右端点的话，不用说直接挂。所以我们可以想办法，减少运算量。首先一个值能整除，肯定就是这个区间内的最小值，所以我们下次就可以直接从最右段开始找，就不用再去再区间内再去暴力了，因为这个最小值已经把能找的斗找到了，所以下面更小的自己在去找自己的范围。

#include <cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<string> #define min(a,b) (a<b?a:b) using namespace std; typedef long long ll; const int maxn=3e5+10; int val[maxn]; vector<int> v; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&val[i]); int max_len=0; for(int i=0;i<n;i++){ if(val[i]==1){ printf("1 %d\n",n-1); printf("1\n"); return 0; } int j=i; while((j+1 < n)&&val[j+1]%val[i]==0) j++; int k=i; while((k-1>=0)&&val[k-1]%val[i]==0) k--; if(j-k>max_len){ max_len=j-k; v.clear(); v.push_back(k); } else if(j-k==max_len){ v.push_back(k); } i=j;//只要这个a[i]是l->r，的因子，就说明是这个区域内的最小点，我们就可以直接从r+1,开始看，往两边遍历 } printf("%d %d\n",v.size(),max_len); for(int i=0;i<v.size();i++){ if(i==0) printf("%d",v[i]+1); else printf(" %d",v[i]+1); } printf("\n"); return 0; }