Мытье посуды
Бесси и Элси помогают фермеру Джону мыть посуду. Это немного сложный процесс, чем можно было бы подумать, из-за отсутствия у них противостоящих пальцев.
Две коровы решили, что Бесси будет наносить мыло, а Элси ополаскивать. Бесси дается грязная стопка тарелок с пометками от 1 до n. У Элси пустая стопка, куда отправляются чистые тарелки. Между Бесси и Элси есть прилавок для мыльных стопок.
На каждом этапе происходит одно из двух:
Бесси берет тарелку с грязной стопки, наносит на нее мыло и ставит на прилавок. Помещая мыльную тарелку на стойку, Бесси должна либо (i) поставить тарелку поверх существующей непустой мыльной стопки, либо (ii) создать новую мыльную стопку справа от всех существующих мыльных стопок.
Элси берет тарелку из верхней части крайней левой мыльной стопки. Элси ополаскивает тарелку и кладет ее на чистую стопку.
Цель состоит в том, чтобы в чистой стопке все тарелки были расположены по порядку: тарелка с наименьшим номером внизу, а с наибольшим номером вверху. Коровы могут оказаться не в состоянии достичь этой цели для всей стопки тарелок, поэтому, определите длину наибольшего префикса входного порядка, для которого эта цель достижима.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 10^5). В следующих n строках указывается порядок блюд в стопке Бесси, причем первое число - это блюдо на вершине стопки.
Выходные данные
Выведите длину самого длинного префикса входной стопки, который можно успешно помыть, чтобы тарелки были правильно упорядочены в чистой стопке.