CodeForces - 359D

86 阅读 0 评论 57 点赞

我是靠谱客的博主优美曲奇，这篇文章主要介绍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

复制代码

Output

复制代码

Input

复制代码

Output

复制代码

Input

复制代码

Output

复制代码

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
}