Беси и Эльза помогают Фермеру Джону мыть посуду.
Они решили, что Беси будет мыть посуду со средством, а Эльза - полоскать.
Беси получила поднос грязных тарелок пронумерованных от \(1\) до \(N\)
(\(1 \leq N \leq 10^5\)). Эльза получил пустой поднос, куда она должна
выкладывать чистые тарелки.
Между Беси и Эльзой имеется поднос тарелок помытых со средством.
На каждом шагу происходит одно из следующих событий
-
Беси берёт тарелку с вершины стека грязных тарелок, моет со средством и
помещает на поднос тарелок, помытых со средством. Когда Беси кладёт тарелку помытую со средством в стек, она или кладёт её наверх существующего не пустого стека таких тарелок,
или создаёт новый стек справа от всех существующих тарелок, помытых со средством.
-
Эльза берёт тарелку сверху самого левого стека, Эльза ополаскивает тарелку и
кладёт её на вершину стека с чистыми тарелками.
Цель - получить стек с чистыми тарелками по порядку так, чтобы минимальный
номер был в самом низу, а максимальный - в самом верху. Может получится, что это
невозможно, тогда определите длину наибольшего префикса ввода, для которого
такая цель достижима.
ФОРМАТ ВВОДА (файл dishes.in):
Первая строка ввода содержит \(N\). Следующие \(N\) строк указывают порядок тарелок
в стеке Беси, первое число соответствует вершине стека.
ФОРМАТ ВЫВОДА (файл dishes.out):
Выведите длину наибольшего префикса входного стека, который можно успешно помыть
так, что тарелки окажутся в правильном порядке на чистом подносе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
5
2
3
1
|
4
|