Codeforces Round 879 (Div. 2) |
---|
Закончено |
Недавно Поликарпу подарили необычную печатную машинку!
Машинка состоит из $$$n$$$ ячеек, пронумерованных слева направо от $$$1$$$ до $$$n$$$, и движущейся над ними каретки. В ячейках печатной машинки лежат $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, причем в каждой ячейке $$$i$$$ изначально лежит число $$$p_i$$$. До всех действий каретка находится на ячейке с номером $$$1$$$ и в ее буферном хранилище ничего нет. Назовем ячейку текущей, если каретка стоит на этой ячейке.
Она может выполнять пять типов операций:
Поликарпа очень заинтересовала эта печатная машинка, поэтому он просит вас помочь разобраться в ней и задаст вам $$$q$$$ запросов трех типов:
До всех запросов, а также после каждого запроса Поликарп хочет узнать, какое минимальное количество сбросов каретки нужно сделать для текущей последовательности, чтобы распределить числа по своим ячейкам (то есть чтобы число $$$i$$$ оказалось в ячейке с номером $$$i$$$).
Обратите внимание, что Поликарп хочет только узнать минимальное количество сбросов каретки для расположения чисел по своим местам, но он не распределяет их на самом деле.
Помогите Поликарпу узнать ответы на интересующие его запросы!
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — количество ячеек.
Вторая строка содержит $$$n$$$ целых различных чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — изначальное расположение чисел по ячейкам.
Третья строка содержит единственное число $$$q$$$ ($$$0 \le q \le 4 \cdot 10^5$$$) — количество запросов.
В каждой из следующих $$$q$$$ строках описываются запросы Поликарпа:
В $$$j$$$-й строке сначала содержится число $$$t_j$$$ ($$$1 \le t_j \le 3$$$) — тип запроса .
Если запрос типа $$$t_j = 1$$$ или $$$t_j = 2$$$, то далее, в той же строке, содержится число $$$k_j$$$ ($$$1 \le k_j \le n$$$) — длина сдвига.
Выведите $$$q + 1$$$ число — минимальное количество сбросов каретки для последовательности до всех запросов, а также после каждого запроса Поликарпа.
3 2 3 1 0
1
3 1 2 3 2 2 1 3
0 2 1
5 3 1 2 5 4 5 1 3 3 2 3 1 4 3
3 2 1 2 1 2
В первом примере ответ $$$1$$$. Картинка ниже показывает работу каретки.
Во втором примере последовательности, для которых нужно посчитать ответ, выглядят так:
В третьем примере последовательности до всех запросов и после каждого запроса выглядят так:
Название |
---|