Задача №112803. Очередь в банк
Недавно Скрудж устроился работать охранником в банке. Работа скучная, делать нечего, поэтому он начал следить за очередью. Исходно в очереди стоит n человек. Так как до этого несколько лет Скрудж работал психологом, он смог довольно точно оценить настроение каждого человека в очереди. Скрудж пронумеровал людей в очереди по порядку, начиная с нуля, таким образом получилось, что номер человека в очереди равен числу людей, которое стоит в очереди перед ним. Настроение \(i\)-го человека он описал целым неотрицательным числом \(a_i\). Скрудж считает, что у человека хорошее настроение, если оно не меньше \(x\). Если это не так, то настроение у человека плохое.
Люди приходят в очередь, уходят из нее. Если в очередь приходит новый человек, Скрудж мгновенно оценивает его настроение, и с течением времени оно не меняется.
Теперь Скрудж придумал себе следующее занятие: в некоторые моменты времени он выбирает одного человека из очереди и считает, сколько перед ним стоит человек с хорошим настроением. Это занятие уже показалось ему интересным, и он решил придумать, как его можно автоматизировать. Так как сам Скрудж не силен в программировании, помощи в решении этой задачи он попросил у вас. Помогите ему!
В первой строке входного файла даны два числа \(n, x\) (\(1 \leq n \leq 100\, 000, 0 \leq x \leq 10^9\)) — начальное количество человек в очереди и нижняя граница хорошего настроения.
В следующей строке даны \(n\) чисел \(a_i\) — настроения людей в очереди (\(0 \leq a_i \leq 10^9\)).
В третьей строке входного файла дано число \(m\) (\(1 \leq m \leq 100\, 000\)) — количество событий, которые происходили с очередью. В следующих \(m\) строках дано описание событий. Событие описывается одним из трех способов:
- 1 a (0 ≤ a ≤ 109) — в конец очереди приходит человек с настроением, равным a.
- 2 — из очереди уходит человек, перед которым никого не стоит (в нумерации Скруджа он имеет номер 0). После этого Скрудж мысленно уменьшает номера людей в очереди на 1.
- 3 i — Скрудж хочет узнать, сколько людей с хорошим настроением стоит перед человеком, перед которым в очереди в этот момент стоит i человек.
Гарантируется, что все запросы корректны: если в очереди никого нет, то операция второго типа не выполняется, а количество человек в очереди всегда будет строго больше \(i\) в запросе третьего типа.
На каждый запрос третьего типа в отдельной строке выходного файла выведите одно число — количество человек с хорошим настроением, которые стоят перед человеком с данным номером.
1 2 3 5 1 2 1 1 3 0 3 1 3 2
0 1 2
2 2 1 2 7 3 0 3 1 2 3 0 1 3 3 0 3 1
0 0 0 0 1
Первая группа тестов состоит из тестов, для которых выполняется ограничение \(n, m \leq 1\, 000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение \(n, m \leq 100\, 000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 60 баллов.