Consecutive Subsequence CodeForces - 977F （map优化DP）·

You are given an integer array of length n

You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to [x,x+1,…,x+k−1]

Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array [5,3,1,2,4]

Input

The first line of the input containing integer number n

Output

On the first line print k

On the second line print the sequence of the indices of the any maximum length subsequence of the given array that forms an increasing sequence of consecutive integers.

Examples

Input

7
3 3 4 7 5 6 8

Output

4
2 3 5 6

Input

6
1 3 5 2 4 6

Output

2
1 4

Input

4
10 9 8 7

Output

1
1

Input

9
6 7 8 3 4 5 9 10 11

Output

6
1 2 3 7 8 9

Note

All valid answers for the first example (as sequences of indices):

[1,3,5,6]
[2,3,5,6]

All valid answers for the second example:

[1,4]
[2,5]
[3,6]

All valid answers for the third example:

All valid answers for the fourth example:

[1,2,3,7,8,9]

题意：

给定一个含有N个整数的数组，求出最大的长度len，使之数组中可以不连续的子数组时严格递增1的数组，并要求输出这个子数组的每一个元素的下标。

思路：

类似最长上升子序列的问题，但这里的要求是每一次必须递增1，即数值是连续+1 的。

那么我们可以考虑，对于访问到的每一个a[i]时，以a[i]为最后一个数值的子数组的长度dp[a[i]] = dp[a[i]-1] + 1 （即转移方程）

因为a[i]的范围是1~1e9，所以dp不能开数组，而要开map<int,int> dp；

找出子数组的每一个下标。

我用的是一个比较简单的方法。

因为每一次连续递增1的性质，我们只需记录最大的ans值的dp[a[i]] 的下标值i，

那么这个递增的子数组的初始值就是a[i]-ans+1

然后我们O（N）扫一遍数组，以此输出数组中的那些连续的数值的下标即可。

细节见ACODE:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int a[maxn];
map<int,int> m;
map<int,int> pre;
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    int ans=0;
    int id;
    repd(i,1,n)
    {
        m[a[i]]=m[a[i]-1]+1;
        if(m[a[i]]>ans)
        {
            ans = m[a[i]];
            id=i;
        }
        ans = max(ans,m[a[i]]);
    }
    int num=a[id]-ans+1;
    std::vector<int> v;
    int cnt=0;
    repd(i,1,n)
    {
        if(a[i]==num)
        {
            v.pb(i);
            num++;
            cnt++;
        }
    }
    cout<<max(cnt,ans)<<endl;
    for(auto x:v)
    {
        cout<<x<<" ";
    }
    cout<<endl;
    
    
    
    
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}