Вам дан массив целых чисел \(a\) длины \(n\).
Одна операция состоит из:
- Выбора индекса \(i\) такого, что \(1 \le i \le n - 1\) и \(a_i \le a_{i + 1}\).
- Увеличения \(a_i\) на \(1\).
Найдите максимально возможное значение \(\max(a_1, a_2, \ldots a_n)\), которое можно получить, выполнив эту операцию не более \(k\) раз.
Примечание
В первом наборе входных данных одной возможной оптимальной последовательностью операций является: \([\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]\).
Во втором наборе вдодных данных одной возможной оптимальной последовательностью операций является: \([1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]\).