707. Очередь из кандидатов

Не решаласьЛёгкая

За забором завода по производству программ выстроилась очередь из кандидатов, желающих устроиться на работу. Исходно в очереди стоит n n человек. Люди в очереди пронумерованы по порядку, начиная с нуля. Номер человека в очереди равен числу людей, которое стоит в очереди перед ним. В конец очереди могут вставать новые кандидаты, а также из начала очереди кандидаты могут проходить на собеседование.

Вася давно работает в HR, поэтому с одного взгляда умеет оценивать профессионализм кандидата. Профессионализм i i -го человека — целое неотрицательное число a i a_i . Во время стояния в очереди профессионализм кандидата не меняется.

Вася считает кандидата подходящим, если его профессионализм не меньше x x . Если это не так, то кандидат неподходящий.

Иногда к Васе приходит коллега Маша и спрашивает, сколько подходящих кандидатов среди первых k k человек в очереди. Вася хороший HR, но плохой программист (если бы был хорошим — сам бы встал в очередь), так что помогите ему правильно ответить на запросы Маши.

Формат ввода

В первой строке вводятся два числа n n , x x ( 1 ≤ n ≤ 100   000 , 0 ≤ x ≤ 1 09 1 \le n \le 100\,000, 0 \le x \le 10^9 ) — начальное количество кандидатов в очереди и нижняя граница профессионализма.

В следующей строке вводятся n n чисел a i a_i — профессионализм людей в очереди ( 0 ≤ a i ≤ 1 09 0 \le a_i \le 10^9 ).

В третьей строке вводится число m m ( 1 ≤ m ≤ 100   000 1 \le m \le 100\,000 ) — количество событий, которые происходили с очередью. В следующих m m строках дано описание событий. Событие бывает одного из трёх типов:

  • 1 a a ( 0 ≤ a ≤ 1 09 0 \le a \le 10^9 ) — в конец очереди приходит человек с профессионализмом, равным a a .
  • 2 — из начала очереди уходит человек (он имеет номер 0). После этого номера оставшихся в очереди людей уменьшаются на 1.
  • 3 k k ( 0 ≤ k ≤ n 0 \le k \le n ) — Маша хочет узнать, сколько подходящих людей среди первых k k человек в очереди.

Гарантируется, что все запросы корректны: если в очереди никого нет, то операция второго типа не выполняется, а количество человек в очереди всегда будет строго больше k k в запросе третьего типа.

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

На каждый запрос третьего типа в отдельной строке выведите одно число — количество подходящих кандидатов.

Ограничения

Ограничение времени
2 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
1 2
3
5
1 2
1 1
3 0
3 1
3 2
Вывод
0
1
2

Пример 2

Ввод
2 2
1 2
7
3 0
3 1
2
3 0
1 3
3 0
3 1
Вывод
0
0
0
0
1

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти