[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