Миття посуду

Бессі та Елсі допомагають фермеру Джону мити посуд. Це трохи складніше, ніж можна було б подумати, через відсутність у них протиставлених пальців.

Дві корови вирішили, що Бессі буде наносити мило, а Елсі ополіскувати. Бессі отримує брудну стопку тарілок з номерами від $1$ до $n$. У Елсі є порожня стопка для чистих тарілок. Між ними знаходиться прилавок для мильних стопок.

На кожному етапі відбувається одне з двох:

• Бессі бере тарілку з брудної стопки, наносить на неї мило і ставить на прилавок. Вона може або (i) покласти тарілку на існуючу мильну стопку, або (ii) створити нову мильну стопку праворуч від усіх існуючих.

• Елсі бере тарілку з верхньої частини крайньої лівої мильної стопки. Вона ополіскує тарілку і кладе її на чисту стопку.

Мета полягає в тому, щоб у чистій стопці всі тарілки були розташовані по порядку: тарілка з найменшим номером внизу, а з найбільшим номером вгорі. Корови можуть не завжди досягти цієї мети для всієї стопки тарілок, тому визначте довжину найбільшого префікса вхідного порядку, для якого ця мета досяжна.