28979번 - Взрывопотам 다국어

Стоило Ньюту немного отвлечься от присмотра за своим зверинцем, как у него сразу сбежал взрывопотам. Ньют должен поймать его как можно быстрее, пока он не разнес половину города.

Взрывопотамы --- странные существа, их поведение может озадачить или даже напугать человека, не видевшего их раньше. На авеню, на которой Ньют будет ловить взрывопотама, стоят в ряд $n$ фонарных столбов разной высоты. Волшебник собирается встать около одного из них и приманить взрывопотама. Разъяренный взрывопотам прибежит к этому столбу и начнет крушить все большие столбы, который он увидит. Точнее, он сломает столб около Ньюта, побежит к ближайшему справа столбу, который строго выше чем столб Ньюта, сломает его и продолжит так же ломать столбы справа, ломая ближайший справа столб, который выше последнего сломанного.

Ньют хоть и рассеянный, но магией владеет хорошо. Особенно хорошо ему удаются пространственные преобразования: он может применить заклинание, которое перенесет несколько самых левых столбов в конец улицы, поставив их в таком же порядке после последнего столба. Например, если на улице стояли столбы высотой 2, 4, 1, 3, 3, и чародей применит заклинание к первым двум столбам, то после этого столбы будут стоять на улице в порядке 1, 3, 3, 2, 4.

Чем больше столбов снесет взрывопотам, тем сильнее он устанет, и его будет проще поймать. Помогите Ньюту определить, какое максимальное количество столбов сломает взрывопотам, если волшебник может один раз перенести несколько столбов из начала улицы в конец и после этого встать около любого столба.

В первой строке дано одно целое число $n$ --- количество фонарей на авеню ($1 \le n \le 200\,000$).

В следующей строке дано $n$ целых чисел $a_i$ --- высоты фонарей в порядке от начала авеню к концу ($1 \le a_i \le 10^9$).

Выведите одно целое число --- максимальное число столбов, которое может сломать взрывопотам.