A sequence of n integers is called smooth, if the absolute values of the differences between successive numbers are at most d. We call a non-smooth sequence semi-smooth, if we can change exactly one number in the sequence to make it smooth. For example, let n = 4 and d = 5. The sequence 21, 20, 18, 20 is smooth, since each pair of adjacent numbers has a gap smaller than 5. The sequence 21, -8, 20, 20 is semi-smooth, since we can replace -8 with 20 to make it smooth.

Write a program to test if a sequence of integers is smooth or semi-smooth.

Technical Specification

1. All integers in the sequence have absolute values bounded by 220.

2. 1 ≤ n,d ≤ 1000.

Input

An instance of the problem consists of the size n of the sequence, and the gap d in a line. They are positive integers in the range [1, 1000]. Then n integers, separated with space(s), follow in the next line.

Note that the test data file may contain more than one instance. The last instance is followed by a line containing a single ‘0’.

Output

For each instance, output ‘Y’, if the sequence is smooth or semi-smooth in a separate line. Otherwise, output ‘N’.

Sample Input

3 2

2 4 6

3 1

3 5 7

0

Sample Output 

Y

N

做得有点自闭了QAQ

WA3次orzorzorz

思路：

从前向后扫一遍，

当abs(a[i]-a[i+1])>d时，

1.若abs(a[i+1]-a[i+2])>d，说明a[i+1]必须需要更改

      （1）如果abs(a[i]-a[i+2])>2*d，说明a[i+1]没有合适的值满足题意，NO；

      （2）否则此处可以修改。

2.否则需要修改a[i]和a[i+1]中的一个

      （1）如果abs(a[i-1]-a[i+2])>3*d，说明无法做出合适的修改，NO；

      （2）否则此处可以修改。

当需要修改的数的个数多于1个时，NO。

 

边界啊边界！！！！！！！！！！！！！！！QWQWQ

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
const int N=1e4+30;
ll a[N];
int main()
{
    int n,d;
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&d);
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
        }
        a[0]=a[1];
        a[n+1]=a[n];
        int cnt=0;
        bool flag=1;
        for(int i=1; i<n; i++)
        {
            if(cnt>1)
            {
                flag=0;
                break;
            }
            if(abs(a[i]-a[i+1])>d)
            {
                if(abs(a[i+1]-a[i+2])>d)
                {
                    cnt++;
                    if(abs(a[i+2]-a[i])>2*d)
                    {
                        flag=0;
                        break;
                    }
                    i++;
                }
                else
                {
                    if(i==1&&abs(a[i-1]-a[i+2])>3*d)
                    {
                        flag=0;
                        break;
                    }
                    cnt++;
                }
            }
        }
        if(flag&&cnt<=1)
            cout<<"Y"<<'\n';
        else
            cout<<"N"<<'\n';
    }
    return 0;
}