C. Алёна и башни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алёны есть 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 Алёна хотела бы знать максимальную ширину горы. Ширина непрерывной последовательности башен равна количеству башен в ней.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 3·105) — количество башен из кубиков.

Во второй строке находятся n целых чисел — a1, a2, ..., an (1 ≤ ai ≤ 109) — количество кубиков в каждой башне.

В третьей строке находится целое число m (1 ≤ m ≤ 3·105) — количество запросов.

В следующих m строках находятся по 3 числа. В i-й из этих строк записаны целые числа li, ri и di (1 ≤ l ≤ r ≤ n, 1 ≤ di ≤ 109), которые обозначают, что нужно на каждую башню с li-й по ri-ю положить сверху по di кубиков.

Выходные данные

Выведите m строк. В i-й строке выведите максимальную ширину горы после обработки i-го запроса.

Пример
Входные данные
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1
Выходные данные
2
4
5
Примечание

Рассмотрим тест из условия:

После добавления по 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.