#P6099. [USACO19FEB] Dishwashing G

[USACO19FEB] Dishwashing G

题目背景

Bessie 和 Elsie 正在帮助 Farmer John 洗碗,这是一个比人们想象的更复杂的过程。

题目描述

两头奶牛决定 Bessie 负责涂肥皂,Elsie 负责冲洗。

刚开始的时候,NN 个脏盘子(保证是从 11NN 的一个排列)堆在 Bessie 那里,而 Elsie 这边的堆是空的。而在她们俩之间,则有一张专门放涂过肥皂的盘子的桌子。

每个冲洗步骤需要执行以下两个操作之一:

  • Bessie 从脏盘子堆顶取出一个盘子,涂上肥皂,然后放在桌子上。将这个盘子放在桌子上时,Bessie 只能放在现有的非空盘堆的顶端,或是在最右边新增一个盘堆。
  • Elsie 从桌子最左边的盘堆的顶端拿起盘子,将它冲洗后放在干净的盘堆顶端。

她们希望干净的盘堆能按编号排序,编号最小的在底端,编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序,请你求出一个最大前缀,使得该前缀的所有盘子洗干净后,能按上面的要求堆叠。

输入格式

第一行一个整数 NN1N1051 \leq N \leq 10^5)。

接下来 NN 行,每行一个整数,代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。

输出格式

输出该序列的最大前缀长度,使得该前缀的所有盘子洗干净后,能按小号在下,大号在上的规则堆叠。

5
4
5
2
3
1
4