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
Formally, we are interested in finding the length of the longest increasing subsequence (LIS) of
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
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
The second line contains
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
Comments