Испытание

시간 제한2초메모리 제한1024 MB

요약

배열의 모든 원소에 비트 OR과 AND 연산을 차례로 적용하면서, 각 연산 후에 배열을 나눌 수 있는 비감소 연속 구간의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 세그먼트 트리, 구현, 배열
정답자: 아직 제출이 없습니다

문제

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

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

OR x --- к каждому элементу массива применить операцию побитового <<ИЛИ>> с числом $x$ (то есть $f\_i = f\_i\\,|\\,x$ для всех $1 \leq i \leq n$ ).
AND x --- к каждому элементу массива применить операцию побитового <<И>> с числом $x$ (то есть $f\_i = f\_i\\\&x$ для всех $1 \leq i \leq n$ ).

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

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

입력

Первая строка входных данных содержит натуральное число $n$ --- размер массива $f$ ( $1 \le n \le 10^5$ ).

Во второй строке находятся $n$ целых чисел $f\_i$ --- исходные элементы массива ( $0 \le f\_i \le 10^9$ ).

Третья строка содержит число $m$ --- количество операций ( $1 \le m \le 10^5$ ). Следующие $m$ строк содержат сами операции. Каждая строка содержит тип операции и целое число $x$ , в формате, указанном в условии ( $0 \le x \le 10^9$ ).

출력

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

예제1

예제 1
입력
```
3
1 2 4
2
OR 1
AND 3
```
예상 출력
```
1
2
```