Есть ряд из \(n\) цветов, у \(i\)-го из них изначально высота \(h_i\) метров.
Каждую секунду порыв ветра слева будет понижать высоты некоторых цветов.
А именно, каждую секунду, для каждого \(i\) от \(1\) до \(n\) в этом порядке, происходит следующее:
- Если \(i = n\) или \(h_i > h_{i + 1}\), значение \(h_i\) меняется на \(\max(0, h_i - 1)\).
Сколько секунд пройдёт перед тем, как \(h_i=0\) будет впервые верно для всех \(1 \le i \le n\)?
Выходные данные
Для каждого набора входных данных, выведите одно целое число — количество секунд, которое пройдёт перед тем, как \(h_i=0\) будет впервые верно для всех \(1 \le i \le n\).
Примечание
В первом наборе входных данных высоты цветов меняются следующим образом: \([1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]\).
Во втором наборе входных данных высоты цветов меняются следующим образом: \([3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 1 2
2
3 1
1
9
5
7 4 4 3 2
|
4
3
9
7
|