У Алфена есть массив целых положительных чисел \(a\) длины \(n\).
Алфен может применять следующую операцию:
- Для всех \(i\) от \(1\) до \(n\), заменить \(a_i\) на \(\max(0, a_i - 1)\).
Алфен будет применять указанную выше операцию до тех пор, пока \(a\) не окажется отсортированным, то есть пока для \(a\) не станет верно \(a_1 \leq a_2 \leq \ldots \leq a_n\). Сколько операций применит Алфен? В рамках ограничений задачи можно утверждать, что Алфен применит конечное число операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество операций, которых применит Алфен.
Примечание
В первом наборе входных данных \(a=[1,2,3]\). Поскольку \(a\) уже отсортирован, Алфен не будет применять никаких операций. Поэтому ответ равен \(0\).
Во втором наборе входных данных \(a=[2,1,2,1,2]\). Поскольку \(a\) изначально не отсортирован, Алфен применит операцию, чтобы стало \(a=[1,0,1,0,1]\). После применения одной операции \(a\) всё ещё не отсортирован, поэтому Алфен применит еще одну операцию, чтобы стало \(a=[0,0,0,0,0]\). Поскольку \(a\) теперь отсортирован, Алфен больше применять операцию не будет. Поскольку Алфен выполнил в общей сложности две операции, ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
1 2 3
5
2 1 2 1 2
4
3 1 5 4
2
7 7
5
4 1 3 2 5
5
2 3 1 4 5
3
1000000000 1 2
|
0
2
5
0
4
3
1000000000
|