No tag edit access

D. Remove One Element

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

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.

Examples

Input

5 1 2 5 3 4

Output

4

Input

2 1 2

Output

2

Input

7 6 5 4 3 2 4 3

Output

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$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 13:56:46 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|