시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB186776944.805%

문제

Global warming is an important issue and Johnny knows about it. He decided to make an analysis of historical temperatures and find a subsequence of days (not necessarily consecutive) where the temperature was strictly increasing. It will convince the non-believers!

Johnny has found historical data from n consecutive days. The temperature on the i-th day was ti.

Formally, we are interested in finding the length of the longest increasing subsequence (LIS) of (t1, t2, . . . , tn), that is, the largest possible k for which it is possible to choose an increasing sequence of indices 1 ≤ a1 < a2 <. . . < ak ≤ n such that ta1 < ta2 < . . . < tak.

Johnny wants to find a really long subsequence and that is why he decided to cheat a bit. He will first choose a non-empty interval of days and an integer d (−x ≤ d ≤ x) and he will increase the temperature in each of those days by d. A small change like that probably will not be noticed by the community, while at the same time it should make the LIS longer. It is allowed to choose d = 0.

What is the largest possible length of the LIS after a change?

입력

The first line of the standard input contains two space-separated integers n and x (1 ≤ n ≤ 200 000, 0 ≤ x ≤ 109), the number of days and the limit for the absolute value of d.

The second line contains n integers t1, t2, . . . , tn (1 ≤ ti ≤ 109) separated by spaces, the sequence of historical temperatures.

출력

Print one integer, the largest possible length of the LIS after a single change.

서브태스크

번호 배점 제한
1 5

n, x ≤ 10

2 10

n, x ≤ 50

3 13

n ≤ 1000

4 10

x = 0

5 20

x ≤ 5, n ≤ 50 000

6 17

x = 109

7 25

No additional constraints

예제 입력 1

8 10
7 3 5 12 2 7 3 4

예제 출력 1

5

Johnny can choose an interval [2, 3] and d = −5, which means decreasing t2 and t3 by 5. In this case the new sequence is (7, −2, 0, 12, 2, 7, 3, 4), where he can find a LIS (−2, 0, 2, 3, 4). The length of the LIS is 5.

채점 및 기타 정보

  • 예제는 채점하지 않는다.