[USACO19FEB] Dishwashing G
题目背景
Bessie 和 Elsie 正在帮助 Farmer John 洗碗,这是一个比人们想象的更复杂的过程。
题目描述
两头奶牛决定 Bessie 负责涂肥皂,Elsie 负责冲洗。
刚开始的时候,$N$ 个脏盘子(保证是从 $1$ 到 $N$ 的一个排列)堆在 Bessie 那里,而 Elsie 这边的堆是空的。而在她们俩之间,则有一张专门放涂过肥皂的盘子的桌子。
每个冲洗步骤需要执行以下两个操作之一:
- Bessie 从脏盘子堆顶取出一个盘子,涂上肥皂,然后放在桌子上。将这个盘子放在桌子上时,Bessie 只能放在现有的非空盘堆的顶端,或是在最右边新增一个盘堆。
- Elsie 从桌子最左边的盘堆的顶端拿起盘子,将它冲洗后放在干净的盘堆顶端。
她们希望干净的盘堆能按编号排序,编号最小的在底端,编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序,请你求出一个最大前缀,使得该前缀的所有盘子洗干净后,能按上面的要求堆叠。
输入输出格式
输入格式
第一行一个整数 $N$($1 \leq N \leq 10^5$)。
接下来 $N$ 行,每行一个整数,代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。
输出格式
输出该序列的最大前缀长度,使得该前缀的所有盘子洗干净后,能按小号在下,大号在上的规则堆叠。
输入输出样例
输入样例 #1
5
4
5
2
3
1
输出样例 #1
4