P9147 签到题

著名的【数据删除】是一个热爱旅游的人！这一天他来到了神秘的 ZYL 国度。 入海关的时候他被问到了一个题目，如果答对他就可以顺利到达 ZYL 的首都 ZY 了！身为堂堂【数据删除】，他居然还花了 $10^{-233}$ 秒才想出来做法，实在是有点难的！于是他决定拿来考考你。

给定长度为 $n$ 的序列 $a$，保证 $a_i$ 是**正整数**。你需要选择一个位置 $i$ 并将 $a_i$ 修改为一个**任意的整数**。最大化最长**严格**上升子串的长度。 所谓严格上升子串，就是从序列中选出位置**连续**的若干个数字，满足后一个数字比前一个大（而不能相等或小于）。 如序列 $[1,4,2,3,5]$ 中，子序列 $[2,3,5]$ 就是严格上升子串，而 $[4,2,3]$（不上升）和 $[1,2,3]$（不连续）则不是。

无

无

**【样例解释 \#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$。