Dishwashing

题目描述

Bessie 和 Elsie 正在帮 Farmer John 洗盘子。由于她们缺少可对握的拇指，这个过程比想象中更复杂。 两头奶牛决定由 Bessie 负责抹上肥皂，Elsie 负责冲洗。Bessie 得到一叠脏盘子，盘子编号为 $1$ 到 $N$（$1 \leq N \leq 10^5$）。Elsie 有一个空栈，用来放干净的盘子。Bessie 和 Elsie 之间有一个台面，用来放带肥皂的盘子堆。

在每一步中，执行以下操作之一： Bessie 从脏盘子栈顶取一个盘子，抹上肥皂，然后把它放到台面上。将带肥皂的盘子放到台面上时，Bessie 必须要么 (i) 把盘子放在某个已有的非空带肥皂盘子堆的顶部，要么 (ii) 在所有已有带肥皂盘子堆的右侧新建一个带肥皂盘子堆。 Elsie 从最左侧的带肥皂盘子堆的栈顶取一个盘子。Elsie 冲洗该盘子，然后把它放到干净盘子栈的顶部。

目标是让干净盘子栈中的所有盘子按顺序排列：最小编号在底部，最大编号在顶部。奶牛可能无法对整叠盘子都实现该目标，因此请确定输入顺序的最长前缀长度，使得该目标可以实现。

输入格式

第一行输入 $N$。 接下来的 $N$ 行给出 Bessie 的盘子栈中盘子的顺序，其中第一个数表示栈顶的盘子。

输出格式

请输出输入盘子栈的最长前缀长度，使得这些盘子能够被成功洗完并最终在干净盘子栈中正确有序。

5
4
5
2
3
1

4

提示

题目来源：George Xing

标签: USACO|2019|Gold

来源

USACO|2019|Gold