19763번 - Атомы 다국어

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

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

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

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

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

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

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

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

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

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

Иллюстрация к примеру. Пунктиром выделены сильные связи, которые разрушаются на время действия второго типа. Для каждого действия второго типа выделены отрезок запроса и самая длинная цепочка.