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 consecutive days. The temperature on the
day was
.
Formally, we are interested in finding the length of the longest increasing subsequence (LIS) of ,
that is, the largest possible
for which it is possible to choose an increasing sequence of indices
such that
.
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
and he will increase the temperature in
each of those days by
. 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
.
What is the largest possible length of the LIS after a change?
Input
The first line of the standard input contains two space-separated integers and
, the number of days and the limit for the absolute value of
.
The second line contains integers
separated by spaces, the sequence of
historical temperatures.
Output
Print one integer, the largest possible length of the LIS after a single change.
Grading
The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.
Subtask | Constraints | Points |
---|---|---|
no additional constraints |
Sample Input
8 10
7 3 5 12 2 7 3 4
Sample Output
5
Explanation of Sample Output
Johnny can choose an interval and
, which means decreasing
and
by
. In this case the new sequence is
, where he can find a LIS
. The
length of the LIS is
.
Comments