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