4. Beautiful Report
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We are given data on the profit of an IT company over $$$n$$$ consecutive days. For an aesthetically pleasing report, we need to select the maximum number of days such that the following two conditions are met:

  • The profit on each subsequent day must be greater than the profit on the preceding day.
  • The difference between the minimum and maximum intervals (distances) between consecutive selected days must be at most one.
Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 10^4$$$).

The next $$$n$$$ lines contain integers in the range from $$$0$$$ to $$$10^5$$$ — the company's profit for each of the $$$n$$$ days.

Output

Output a single integer — the maximum number of days in the report.

Scoring

Subtask 1 (up to 50 points): $$$n \le 10$$$

Subtask 2 (up to 50 points): $$$n \le 5000$$$

Examples
Input
7
4
2
1
3
1
0
5
Output
3
Input
3
3
2
1
Output
1
Note

In the first example, you can select days numbered 2, 4, and 7 for the report.