У Алёны есть n башен из кубиков. Каждый кубик имеет размеры 1 × 1 × 1. Башня представляет из себя ненулевое количество кубиков, стоящих друг на друге. Башни стоят вплотную в один ряд.
Алёна выбирает некую непрерывную последовательность башен и на каждую башню сверху кладет еще сколько-то кубиков. Более формально: Алёна выбирает последовательность башен с li по ri и на каждую из этих башен кладет сверху еще по di кубиков.
Пусть a1, a2, ..., an — высоты башен слева направо. Назовем непрерывную последовательность башен al, al + 1, ..., ar горой, если существует такое k (l ≤ k ≤ r), что al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar.
После каждого добавления di кубиков на непрерывной последовательности башен с li по ri Алёна хотела бы знать максимальную ширину горы. Ширина непрерывной последовательности башен равна количеству башен в ней.
Выходные данные
Выведите m строк. В i-й строке выведите максимальную ширину горы после обработки i-го запроса.
Примечание
Рассмотрим тест из условия:
После добавления по 2 кубика на каждую башню с первой по третью высоты станут равны [7, 7, 7, 5, 5]. Максимальная по ширине гора — [7, 5], следовательно, ответ 2.
После добавления 1 кубика на вторую башню высоты станут равны [7, 8, 7, 5, 5]. Максимальная по ширине гора — [7, 8, 7, 5], следовательно, ответ 4.
После добавления 1 кубика на четвертую башню высоту станут равны [7, 8, 7, 6, 5]. Максимальная по ширине гора — [7, 8, 7, 6, 5], следовательно, ответ 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1
|
2
4
5
|