C. Атомы

2500 мс · 256 МБ · всё или ничего

Атомы пронумерованы от 1 до $n$ ; у $i$ -го заряд $q_i$ . Соседние атомы $i$ и $i+1$ соединены сильной связью, если $q_{i+1} = q_i + 1$ . Цепочка — несколько подряд идущих атомов, соединённых сильными связями.

Запросы двух видов: прибавить $d$ к зарядам атомов с $l$ -го по $r$ -й, и узнать длину наибольшей цепочки среди атомов с $l$ -го по $r$ -й.

Формат ввода

В первой строке $n$ ( $1 \le n \le 10^5$ ). Во второй — $n$ чисел $q_i$ ( $|q_i| \le 10^9$ ). В третьей — $m$ ( $0 \le m \le 10^5$ ). Далее $m$ строк: + l r d — прибавить $d$ на отрезке ( $|d| \le 10^9$ ), или ? l r — длина наибольшей цепочки внутри отрезка.

Формат вывода

Для каждого запроса ? выведите ответ на отдельной строке.

Примеры

ввод

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

вывод

3
3
5

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.