Взрывопотам
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
deepcycle.in
вывод
deepcycle.out

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

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

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

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

Входные данные

В первой строке дано одно целое число n — количество фонарей на авеню (1 ≤ n ≤ 200 000).

В следующей строке дано n целых чисел ai — высоты фонарей в порядке от начала авеню к концу (1 ≤ ai ≤ 109).

Выходные данные

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

Примеры

Входные данные
5
2 4 1 3 3
Выходные данные
3
Входные данные
6
2 5 3 5 1 5
Выходные данные
2