CodeForces - 359D

68 阅读 0 评论 45 点赞

我是靠谱客的博主优美曲奇，最近开发中收集的这篇文章主要介绍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 %dn",n-1);
            printf("1n");
            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 %dn",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;
}