## CEOI '18 P2 - Global Warming

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

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 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 longer. It is allowed to choose .

What is the largest possible length of the 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 after a single change.

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.

#### 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 . The length of the is .