题目描述
今天是 YQH 的生日，她得到了一个长度为 $n$ 排列 $a_1,a_2,\dots,a_n$ 作为生日礼物，这个排列包含了 $1,2,\dots,n$ 里每个元素恰好一次。
由于 YQH 十分喜欢升序，于是她打算把这个排列进行排序使得最后排列升序。但是她发现一个问题：她太笨了，不会各种 $O(n\log n)$ 的排序算法，于是她退而求次，准备使用 $O(n)$ 的“斯大林排序”。
斯大林排序是这样一个过程：
假设我们要排序的序列是 $a_{1,2,\dots,n}$，那么维护一个初始为空的栈，然后从 $1$ 到 $n$ 枚举 $i$：
假如 $a_i$ 比栈顶严格大或者栈为空，那么把 $a_i$ 加入栈中。
否则，此刻有 $a_i$ 小于等于栈顶，那么什么都不干。
最后把栈里的元素从底到顶输出作为结果。
容易发现，这样我们获得就是原排列的一个上升子序列，但是可能会失去太多的元素，比如假如我们要排序 $[5,1,2,3,4]$，我们最后只得到了 $[5]$。
于是 YQH 进行了改进，现在排序变成这样一个过程：
假设我们要排序的序列是 $a_{1,2,\dots,n}$，那么维护一个初始为空的栈，然后从 $1$ 到 $n$ 枚举 $i$：
假如 $a_i$ 比栈顶严格大或者栈为空，那么把 $a_i$ 加入栈中。
否则，此刻有 $a_i$ 小于等于栈顶，那么有两种选择：把栈顶弹出并把 $a_i$ 加入栈中，或什么都不干。注意，你需要保证任意时刻，栈中的元素从底到顶严格单调上升。
最后把栈里的元素从底到顶输出作为结果。
比如现在我们要排序 $[5,1,2,3,4]$，栈的变化是 $[]\to [5]\to [1]\to [1,2]\to [1,2,3]\to [1,2,3,4]$。
容易发现，最后栈的大小与排序时进行的选择有关。YQH 当然希望最后栈越大越好，于是她找到了你，希望你对于她给出的排列，求出最后栈大小的最大值。
输入格式
第一行一个正整数 $n$ 表示排列长度。
第二行 $n$ 个各不相同的整数表示排列。
输出格式
输出一个整数表示答案。
样例
输入1
5 5 1 2 3 4
输出1
4
输入2
6 1 6 5 2 3 4
输出2
4
其中一种栈的变化是 $[]\to [1]\to [1,6]\to [1,5]\to [1,2]\to [1,2,3]\to[1,2,3,4]$。
输入3
5 4 5 1 2 3
输出3
2
唯一一种栈的变化过程为 $[]\to [4]\to[4,5]\to [4,5]\to[4,5]\to[4,5]$。
样例输入/输出 4
见下发文件中的 ex_sort4.in/ex_sort4.ans。
样例输入/输出 5
见下发文件中的 ex_sort5.in/ex_sort5.ans。
数据范围
| 子任务编号 | $n\le$ | 特殊限制 | 分值 |
|---|---|---|---|
| $1$ | $500$ | 无 | $16$ |
| $2$ | $4000$ | $47$ | |
| $3$ | $5\times 10^5$ | A | $11$ |
| $4$ | B | $12$ | |
| $5$ | 无 | $14$ |
特殊限制A：存在一个对原序列的划分 $[l_1,r_1],[l_2,r_2],\dots,[l_m,r_m]$，其中 $l_{i+1}=r_i+1,l_1=1,r_m=n$，使得 $\forall j\in[l_i,r_i],a_j=r_i-(j-l_i)$。
特殊限制B：保证 $a_i$ 随机生成。
对于所有数据，保证 $1\le n\le 5\times10^5$。