#P1272D. Remove One Element
Remove One Element
No submission language available for this problem.
Description
You are given an array $a$ consisting of $n$ integers.
You can remove at most one element from this array. Thus, the final length of the array is $n-1$ or $n$.
Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.
Recall that the contiguous subarray $a$ with indices from $l$ to $r$ is $a[l \dots r] = a_l, a_{l + 1}, \dots, a_r$. The subarray $a[l \dots r]$ is called strictly increasing if $a_l < a_{l+1} < \dots < a_r$.
The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.
Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array $a$ after removing at most one element.
Input
The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.
The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.
Output
Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array $a$ after removing at most one element.
Samples
5
1 2 5 3 4
4
2
1 2
2
7
6 5 4 3 2 4 3
2
Note
In the first example, you can delete $a_3=5$. Then the resulting array will be equal to $[1, 2, 3, 4]$ and the length of its largest increasing subarray will be equal to $4$.