| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 5 | 5 | 100.000% |
Стоило Ньюту немного отвлечься от присмотра за своим зверинцем, как у него сразу сбежал взрывопотам. Ньют должен поймать его как можно быстрее, пока он не разнес половину города.
Взрывопотамы --- странные существа, их поведение может озадачить или даже напугать человека, не видевшего их раньше. На авеню, на которой Ньют будет ловить взрывопотама, стоят в ряд $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$).
Выведите одно целое число --- максимальное число столбов, которое может сломать взрывопотам.
5 2 4 1 3 3
3
6 2 5 3 5 1 5
2