给定一个长度为 $n$ 的序列，你需要找到一个最长的子序列，使得这个子序列的最长上升子序列长度小于原序列的最长上升子序列长度。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 。

输出格式

一行一个正整数，表示最长的合法子序列长度。

样例 $1$

input

6
4 6 5 2 1 3

output

4

样例 $2\sim 7$

见下发文件。

数据范围与提示

对于所有数据，$1\le n\le 5\times 10^5$，$1\le a_i\le 10^9$ 。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$