Рабочее место участника

В лаборатории аномальных материалов антинаучно-исследовательского комплекса "Black Mesa" проводят эксперименты с недавно разработанным графитовым наностержнем. Графитовый наностержень представляет собой `n` последовательно соединенных атомов углерода, находящихся на одной прямой. Каждый атом имеет определенный заряд.

Для проведения эксперимента, стержень располагают вертикально. Пронумеруем атомы от 1 до `n` снизу вверх. Между двумя атомами образуется сильная связь, если это соседние атомы и верхний из них имеет заряд ровно на один больше, чем нижний. Иными словами, атомы `a` и `b` соединены сильной связью, если `a\ =\ b\ +\ 1` и `q_a\ =\ q_b\ +\ 1`, где `q_i` – заряд `i`-го атома. Цепочкой атомов назовем несколько последовательных атомов, соединенных сильными связями.

Вчера был проведен очередной эксперимент. Перед началом эксперимента каждому атому установили определенный заряд: `i`-му атому установили заряд `q_i`.

Во время эксперимента ученые проводили действия двух типов:

1) у всех атомов с номерами от `l_i` до `r_i`, включительно, заряд изменяли на величину `d_i`;

2) временно разрушали все сильные связи атомов, кроме тех, которые соединяют атомы с номерами от `l_i` до `r_i`, включительно, и измеряли длину самой длинной цепочки атомов среди оставшихся сильных связей. Затем восстанавливали все временно разрушенные связи.

Было произведено `m` действий, однако выяснилось, что в результате побочного эффекта эксперимента запись результатов измерений оказалась утеряна. Для продолжения работы с графитовым наностержнем необходимо восстановить результаты вчерашних измерений. К счастью, сохранился план действий, произведенных во время эксперимента. Помогите ученым продолжить исследования, восстановите результаты измерений.

В первой строке находится одно целое число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) – количество атомов в наностержне. Во второй строке находятся `n` чисел `q_i` (`|q_i|\ ≤\ 10^9`) – начальный заряд `i`-го атома. В третьей строке находится одно целое число `m` (`0\ ≤\ m\ ≤\ 100\ 000`) – количество действий в эксперименте. В следующих `m` строках содержится описание эксперимента.

Если строка начинается с символа +, очередное действие – изменение заряда атомов. В таком случае, далее в этой строке находятся три целых числа: `l_i`, `r_i` и `d_i` (`1\ ≤\ l_i\ ≤\ r_i\ ≤\ n`, `|d_i|\ ≤\ 10^9`), которые характеризуют это действие.

Если строка начинается с символа ?, очередное действие – второго типа. В таком случае, далее в этой строке находятся два целых числа: `l_i` и `r_i` (`1\ ≤\ l_i\ ≤\ r_i\ ≤\ n`), которые характеризуют это действие.

Для каждого действия второго типа выведите в новой строке одно число – длину наибольшей цепочки.

6
2 3 4 3 4 4
5
? 1 6
+ 6 6 1
? 2 6
+ 4 6 2
? 1 5

3
3
5