C. Curtains
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Адиль хочет применить полученные знания на практике после окончания университета. Чтобы стать ближе к проектированию «умного дома», Адиль уже сейчас пытается написать что-то своё. Его первый проект — автоматическое управление шторами. Деталей разработки своего проекта Адиль не раскрывает, но на данный момент его у него имеется $$$N$$$ петелек для штор, которые крепятся к карнизу в точках $$$a_1$$$, $$$a_2$$$, ... , $$$a_N$$$ (координаты в см $$$1 \le a_1 \lt a_2 \lt \dots \lt a_N \le 10^5$$$). А его «умный дом» может выполнять запросы вида:

  1. сдвинуть k-ю петельку вправо или влево на 1 см;
  2. сдвинуть k-ю петельку вправо или влево на 1 см.
При этом совпадать петельки в процессе действий не могут — такие действия следует игнорировать. Проект ещё далёк от завершения, а Адилю нужно готовиться к сессии. Чтобы контролировать, насколько сильно провисают шторы, Адилю важно знать максимальное расстояние между соседними петельками после каждого запроса. Обратите внимание, что карниз можно считать бесконечным и координаты могут становится отрицательными в процессе перемещений.
Входные данные

В первой строке целое число $$$N$$$ — число штор, где $$$2 \le N \le 10^5$$$, во второй строке $$$N$$$ целых чисел $$$a_1, a_2, \dots, a_N$$$ — начальное положение штор, где $$$1 \le a_i \le 10^5$$$, в третьей строке целое число $$$Q$$$ — число запросов, где $$$1 \le Q \le 10^5$$$, в следующих $$$Q$$$ строках содержится описания запросов одного из двух видов: «R k» соответствует запросу типа «сдвинуть k-ую петельку вправо на 1 см»; «L k» соответствует запросу типа «сдвинуть k-ую петельку влево на 1 см».

Выходные данные

$$$Q$$$ целых чисел в столбик — максимальное расстояние между соседними шторами после каждого запроса.

Примеры
Входные данные
3
1 5 10
3
R 2
L 3
R 1
Выходные данные
5
5
4
Входные данные
2
1 2
3
R 1
L 2
R 2
Выходные данные
1
1
2