### 问题描述 最长上升子序列（Longest Increasing Subsequence），简称 LIS，指的是一个序列中最长的一个子序列，满足其单调递增。 例如，对于一个序列 $a_1, a_2, a_3, a_4,...,a_i,...,a_n$，存在一个序列 $b_1, b_2,..., b_m$，满足： 1. $1 \le b_1 \lt b_2 \lt ... \lt b_m \le n$。 2. $a_{b_1} \lt a_{b_2} \lt ... \lt a_{b_m}$。 那么我们称 $\lbrace a_{b_1} , a_{b_2} , ... , a_{b_m} \rbrace$ 为 $\lbrace a_i \rbrace$ 的一个上升子序列。 最长的上升子序列就是最长（元素数量最多）的一个上升子序列。 小蓝学到了这个知识点，并且学会一些用来计算 LIS 的常见算法。 于是小蓝向邻居小桥炫耀他学到的新知识，但是小桥显然不会让小蓝如此得意，于是他提出了一个新的问题： 给定一个长度为 $n$ 的序列 $\lbrace a_i \rbrace$，小蓝可以选择其中的一个位置，修改为 $0 \sim 10^{100}$ 中的任何一个整数。具体来说，小蓝可以选择一个位置 $p(p \in [1, n])$，将 $a_p$ 重新赋值为 $0 \sim 10^{100}$ 中的任意一个整数。请问修改过后，最长上升子序列的长度是多少？ 小蓝看到这个问题，两眼一抹黑，于是请你帮他解决这个问题。 ### 输入格式 第一行输入一个整数 $n$。 第二行输入 $n$ 个整数 $a_1, a_2, ..., a_i, ... ,a_n$，用来表示序列 $a$ 的每个值。 ### 输出格式 输出一个整数，表示修改后的最长上升子序列长度。 ### 样例输入 ``` 5 2 5 4 3 7 ``` ### 样例输出 ``` 4 ``` ### 说明 修改 $3$ 为 $5$，得到 $2,5,4,5,7$，得到最长上升子序列为 $2,4,5,7$。 ### 评测数据范围 $1 \le n \le 5 \times 10^3, 0 \le a_i \le 10^9$。