E. Pillars

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Marmot found a row with n pillars. The i-th pillar has the height of hi meters. Starting from one pillar i1, Marmot wants to jump on the pillars i2, ..., ik. (1 ≤ i1 < i2 < ... < ik ≤ n). From a pillar i Marmot can jump on a pillar j only if i < j and |hi - hj| ≥ d, where |x| is the absolute value of the number x.

Now Marmot is asking you find out a jump sequence with maximal length and print it.

Input

The first line contains two integers n and d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).

The second line contains n numbers h1, h2, ..., hn (1 ≤ hi ≤ 1015).

Output

The first line should contain one integer k, the maximal length of a jump sequence.

The second line should contain k integers i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), representing the pillars' indices from the maximal length jump sequence.

If there is more than one maximal length jump sequence, print any.

Sample test(s)

input

5 21 3 6 7 4

output

41 2 3 5

input

10 32 1 3 6 9 11 7 3 20 18

output

61 4 6 7 8 9

Note

In the first example Marmot chooses the pillars 1, 2, 3, 5 with the heights 1, 3, 6, 4. Another jump sequence of length 4 is 1, 2, 4, 5.

题解：这一题是动归加线段树优化。用F[i]表示以i结尾的最长线段长。线段树的每一个区间存储长度在这个区间内的最大F[i]的i值。这样我们处理F[i]的时候就能够在相应的长度区间内查询出最大值。而查询的时间复杂度是log(n)，所以总的复杂度为O（n*log(n)）。在N为10^5的时候可行。

别忘了要输出路径。所以还要用一个数组记录决策。最后倒着输出即可了。

查询的函数要注意...不然总是RUNTIME ERROR。

这一题事实上还能够骗分。就是用传统方法可是仅仅遍历前300个状态就能够过了。

（仅仅能说数据不强吧...）

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;long long a[100005],b[100005];struct tree{    int l,r,k;};struct tree d[400005];  int f[100005],h1,h2,n,d1,way[100005],ans[100005];void buildtree(int l,int r,int k){    d[k].l=l;    d[k].r=r; d[k].k=0;    if (l==r) return ;    else    {        buildtree(l,(l+r)/2,k*2);        buildtree((l+r)/2+1,r,k*2+1);    }}int _count(long long low,long long high,int k){    if (high
          
           =b[t+1]) return _count(low,high,k*2+1);    else    {        int h1=_count(low,b[t],k*2),h2=_count(b[t+1],high,k*2+1);        if (f[h1]>f[h2]) return h1;            else return h2;    }}void find(int k,int p){    if (d[k].l==d[k].r)    {        d[k].k=p;        return ;    }    int t=(d[k].l+d[k].r)/2;    if (a[p]<=b[t]) find(k*2,p);    else find(k*2+1,p);    if (f[p]>f[d[k].k]) d[k].k=p;}int main(){    scanf("%d%d",&n,&d1);    for (int i=1;i<=n;i++)    {        scanf("%I64d",&a[i]);        b[i]=a[i];    }    sort(b+1,b+n+1);    int i=1,n1=1;    while (i!=n+1)    {        while (b[i]==b[i+1]) i++;        b[n1++]=b[i];        i++;    }    n1--;    //n1 is the length    buildtree(1,n1,1);    memset(way,0,sizeof(way));    for (i=1;i<=n;i++)    {        h1=_count(b[1],a[i]-d1,1); h2=_count(a[i]+d1,b[n1],1);        f[i]=max(f[h1],f[h2])+1;        if (h1>=h2 && h1!=0) way[i]=h1;        else if (h1
           
=1;j--) printf("%d ",ans[j]); return 0;}