Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21687. 【NOIP Round #2】排序

统计

题目描述

今天是 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$ $20$
$2$ $4000$ $50$
$3$ $5\times 10^5$ A $10$
$4$ B $10$
$5$ $10$

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