- Описание
- Решения
- Разборы
- Кодерун AI β
707. Очередь из кандидатов
За забором завода по производству программ выстроилась очередь из кандидатов, желающих устроиться на работу. Исходно в очереди стоит человек. Люди в очереди пронумерованы по порядку, начиная с нуля. Номер человека в очереди равен числу людей, которое стоит в очереди перед ним. В конец очереди могут вставать новые кандидаты, а также из начала очереди кандидаты могут проходить на собеседование.
Вася давно работает в HR, поэтому с одного взгляда умеет оценивать профессионализм кандидата. Профессионализм -го человека — целое неотрицательное число . Во время стояния в очереди профессионализм кандидата не меняется.
Вася считает кандидата подходящим, если его профессионализм не меньше . Если это не так, то кандидат неподходящий.
Иногда к Васе приходит коллега Маша и спрашивает, сколько подходящих кандидатов среди первых человек в очереди. Вася хороший HR, но плохой программист (если бы был хорошим — сам бы встал в очередь), так что помогите ему правильно ответить на запросы Маши.
Формат ввода
В первой строке вводятся два числа , ( ) — начальное количество кандидатов в очереди и нижняя граница профессионализма.
В следующей строке вводятся чисел — профессионализм людей в очереди ( ).
В третьей строке вводится число ( ) — количество событий, которые происходили с очередью. В следующих строках дано описание событий. Событие бывает одного из трёх типов:
- 1 ( ) — в конец очереди приходит человек с профессионализмом, равным .
- 2 — из начала очереди уходит человек (он имеет номер 0). После этого номера оставшихся в очереди людей уменьшаются на 1.
- 3 ( ) — Маша хочет узнать, сколько подходящих людей среди первых человек в очереди.
Гарантируется, что все запросы корректны: если в очереди никого нет, то операция второго типа не выполняется, а количество человек в очереди всегда будет строго больше в запросе третьего типа.
Формат вывода
На каждый запрос третьего типа в отдельной строке выведите одно число — количество подходящих кандидатов.
Ограничения
- Ограничение времени
- 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