F. Печатная машинка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Поликарпу подарили необычную печатную машинку!

Машинка состоит из $$$n$$$ ячеек, пронумерованных слева направо от $$$1$$$ до $$$n$$$, и движущейся над ними каретки. В ячейках печатной машинки лежат $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, причем в каждой ячейке $$$i$$$ изначально лежит число $$$p_i$$$. До всех действий каретка находится на ячейке с номером $$$1$$$ и в ее буферном хранилище ничего нет. Назовем ячейку текущей, если каретка стоит на этой ячейке.

Она может выполнять пять типов операций:

  • Взять число из текущей ячейки, если она не пустая, и положить его в буфер каретки, если в нём нет числа (то есть в буфере может быть не более одного числа).
  • Положить число из буфера каретки, если он не пустой, в текущую ячейку, если она пустая.
  • Поменять местами число, которое находится в буфере каретки, с числом, которое находится в текущей ячейке, если буфер и ячейка имеют в себе числа.
  • Сдвинуть каретку с текущей ячейки $$$i$$$ на ячейку $$$i + 1$$$ (если $$$i < n$$$), при этом число в буфере сохраняется.
  • Сбросить каретку, то есть переместить ее на ячейку с номером $$$1$$$, при этом число в буфере сохраняется.

Поликарпа очень заинтересовала эта печатная машинка, поэтому он просит вас помочь разобраться в ней и задаст вам $$$q$$$ запросов трех типов:

  1. Выполнить циклический сдвиг последовательности $$$p$$$ на $$$k_j$$$ влево.
  2. Выполнить циклический сдвиг последовательности $$$p$$$ на $$$k_j$$$ вправо.
  3. Развернуть последовательность $$$p$$$.

До всех запросов, а также после каждого запроса Поликарп хочет узнать, какое минимальное количество сбросов каретки нужно сделать для текущей последовательности, чтобы распределить числа по своим ячейкам (то есть чтобы число $$$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$$$. Картинка ниже показывает работу каретки.

Во втором примере последовательности, для которых нужно посчитать ответ, выглядят так:

  1. До всех запросов: $$$1\ 2\ 3$$$ — ответ $$$0$$$.
  2. После сдвига на $$$1$$$ вправо: $$$3\ 1\ 2$$$ — ответ $$$2$$$.
  3. После разворота последовательности: $$$2\ 1\ 3$$$ — ответ $$$1$$$.

В третьем примере последовательности до всех запросов и после каждого запроса выглядят так:

  1. $$$3\ 1\ 2\ 5\ 4$$$ — ответ $$$3$$$.
  2. $$$5\ 4\ 3\ 1\ 2$$$ — ответ $$$2$$$.
  3. $$$2\ 1\ 3\ 4\ 5$$$ — ответ $$$1$$$.
  4. $$$3\ 4\ 5\ 2\ 1$$$ — ответ $$$2$$$.
  5. $$$1\ 3\ 4\ 5\ 2$$$ — ответ $$$1$$$.
  6. $$$2\ 5\ 4\ 3\ 1$$$ — ответ $$$2$$$.