Испытание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После схватки с Хелой Тор свалился на весьма странную планету Сакаар. Его сразу же захватили и отправили в качестве гладиатора на арену принимать участие в битве чемпионов Грандмастера, правителя планеты. Первое же испытание оказалось не физическим, а умственным, и показалось Тору чрезвычайно тяжелым.

Первоначально герою дали массив f из n чисел и поставили перед ним непосильную задачу: применить к массиву определенное количество раз запрашиваемые операции и после каждой операции ответить верно на вопрос, озвученный ниже. Операции бывают двух видов:

После каждой операции Тор должен назвать минимальное число непрерывных отрезков массива, на каждом из которых элементы расположены в неубывающем порядке.

Если вы желаете, чтобы Тор одержал победу в битве, помогите ему справиться с поставленной задачей. Только ваши усилия способны ему помочь!

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

Первая строка входных данных содержит натуральное число n — размер массива f (1 ≤ n ≤ 105).

Во второй строке находятся n целых чисел fi — исходные элементы массива (0 ≤ fi ≤ 109).

Третья строка содержит число m — количество операций (1 ≤ m ≤ 105). Следующие m строк содержат сами операции. Каждая строка содержит тип операции и целое число x, в формате, указанном в условии (0 ≤ x ≤ 109).

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

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

Пример

Входные данные
3
1 2 4
2
OR 1
AND 3
Выходные данные
1
2