Description

给定长度为 $n$ 的序列 $a$，保证 $a_i$ 是正整数。你需要选择一个位置 $i$ 并将 $a_i$ 修改为一个任意的整数。最大化最长严格上升子串的长度。

所谓严格上升子串，就是从序列中选出位置连续的若干个数字，满足后一个数字比前一个大（而不能相等或小于）。

如序列 $[1,4,2,3,5]$ 中，子序列 $[2,3,5]$ 就是严格上升子串，而 $[4,2,3]$（不上升）和 $[1,2,3]$（不连续）则不是。

Input Format

第一行，一个正整数 $n$，表示序列的长度。

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示序列 $a$。

Output Format

输出一行一个整数，表示修改后，你最大化的最长严格上升子串的长度。

5
1 4 2 2 3

3

5
1 2 3 2 1

4

5
1 2 3 1 5

5

6
8 2 3 1 4 5

4

6
7 2 9 4 5 6

5

Hint

【样例解释 #1】

对于样例 #1，我们可以将序列 $[1,4,2,2,3]$ 中的第三个位置修改为 $5$，得到新序列 $[1,4,5,2,3]$。这个序列的最长严格上升子串是 $[1,4,5]$，长度为 $3$。

容易证明，不存在一种修改方案使得修改后的序列的最长严格上升子串的长度大于 $3$。

【样例解释 #4】

对于样例 #4，我们可以将序列 $[8,2,3,1,4,5]$ 中的第三个位置修改为 $0$，得到新序列 $[8,2,0,1,4,5]$。这个序列的最长严格上升子串是 $[0,1,4,5]$，长度为 $4$。

容易证明，不存在一种修改方案使得修改后的序列的最长严格上升子串的长度大于 $4$。

【数据范围】

对于前 $20\%$ 的数据，满足 $n \le 5$，$a_i \le 5$。
对于前 $40\%$ 的数据，满足 $n \le 10$，$a_i \le 10$。
对于前 $70\%$ 的数据，满足 $n \le 300$。
对于 $100 \%$ 的数据，满足 $1 \le n \le {10}^6$，$1 \le a_i \le {10}^9$。