Перед вами \(n\) кучек песка, и в \(i\)-й кучке ровно \(a_i\) песчинок. Назовем \(i\)-ю кучку слишком высокой, если \(1 < i < n\), и \(a_i > a_{i-1} + a_{i+1}\). Иными словами кучка слишком высокая, если в ней больше песка, чем в двух соседних вместе. (Обратите внимание, что кучки по краям не могут быть слишком высокими.)
Вам дано целое число \(k\). За одну операцию вы можете выбрать \(k\) последовательных кучек и добавить к каждой из них одну песчинку. Формально, выберите \(1 \leq l,r \leq n\) такие, что \(r-l+1=k\). Затем для всех \(l \leq i \leq r\) обновите \(a_i \gets a_i+1\).
Какое максимальное количество кучек одновременно может быть слишком высокими после нескольких (возможно, нуля) операций?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество кучек, которые одновременно могут быть слишком высокими после нескольких (возможно, нуля) операций.
Примечание
В первом примере можно выполнить следующие три операции:
- Добавить одну песчинку в кучки \(1\) и \(2\): \([\color{red}{3}, \color{red}{10}, 2, 4, 1]\).
- Добавить одну песчинку в кучки \(4\) и \(5\): \([3, 10, 2, \color{red}{5}, \color{red}{2}]\).
- Добавить одну песчинку в кучки \(3\) и \(4\): \([3, 10, \color{red}{3}, \color{red}{6}, 2]\).
После этого кучки
\(2\) и
\(4\) слишком высокие, поэтому ответ в данном случае равен
\(2\). Можно показать, что нельзя сделать более
\(2\) кучек слишком высокими.
Во втором примере любая операция увеличивает все кучки на \(1\), поэтому количество слишком высоких кучек всегда будет \(0\).
В третьем примере можно увеличивать любую кучку на \(1\). Можно показать, что максимальное количество слишком высоких кучек равно \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1
|
2
0
1
|