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