Стоило Ньюту немного отвлечься от присмотра за своим зверинцем, как у него сразу сбежал взрывопотам. Ньют должен поймать его как можно быстрее, пока он не разнес половину города.
Взрывопотамы — странные существа, их поведение может озадачить или даже напугать человека, не видевшего их раньше. На авеню, на которой Ньют будет ловить взрывопотама, стоят в ряд 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