시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

В лаборатории аномальных материалов антинаучно-исследовательского комплекса <<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$), которые характеризуют это действие.

출력

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

예제 입력 1

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

예제 출력 1

3
3
5

힌트

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