题目描述

今天是 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。

数据范围

特殊限制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$。