|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||143||67||55||45.455%|
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.
8 10 7 3 5 12 2 7 3 4
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.