| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 6 | 5 | 3 | 100.000% |
В лаборатории аномальных материалов антинаучно-исследовательского комплекса <<Black Mesa>> проводят эксперименты с недавно разработанным графитовым наностержнем. Графитовый наностержень представляет собой $n$ последовательно соединенных атомов углерода, находящихся на одной прямой. Каждый атом имеет определенный заряд.
Для проведения эксперимента, стержень располагают вертикально. Пронумеруем атомы от 1 до $n$ снизу вверх. Между двумя атомами образуется сильная связь, если это соседние атомы и верхний из них имеет заряд ровно на один больше, чем нижний. Иными словами, атомы $a$ и $b$ соединены сильной связью, если $a = b + 1$ и $q_a = q_b + 1$, где $q_i$ --- заряд $i$-го атома. Цепочкой атомов назовем несколько последовательных атомов, соединенных сильными связями.
Вчера был проведен очередной эксперимент. Перед началом эксперимента каждому атому установили определенный заряд: $i$-му атому установили заряд $q_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$), которые характеризуют это действие.
Для каждого действия второго типа выведите в новой строке одно число --- длину наибольшей цепочки.
6 2 3 4 3 4 4 5 ? 1 6 + 6 6 1 ? 2 6 + 4 6 2 ? 1 5
3 3 5
Иллюстрация к примеру. Пунктиром выделены сильные связи, которые разрушаются на время действия второго типа. Для каждого действия второго типа выделены отрезок запроса и самая длинная цепочка.