B2. Побрей бобра!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер недавно спроектировал и построил нанотехнологичный инновационный универсальный инструмент массового обривания бобров — «Брабобрей-5000». Брабобрей-5000 умеет обривать бобров целыми семьями! Как он работает? Очень просто!

Имеется n бобров, каждый из них имеет уникальный номер от 1 до n. Рассмотрим перестановку a1, a2, ..., an этих n бобров. Брабобрей-5000 за один запуск может обрить бобров с номерами от x до y (включительно) тогда и только тогда, когда найдутся такие индексы i1 < i2 < ... < ik, что ai1 = x, ai2 = x + 1, ..., aik - 1 = y - 1, aik = y. И это действительно очень удобно. Например, перестановку бобров 1, 2, 3, ..., n можно обрить за один раз.

Если за один запуск обрить бобров с x по y нельзя, то можно найти такое разбиение на группы [x, p1], [p1 + 1, p2], ..., [pm + 1, y] (x ≤ p1 < p2 < ... < pm < y), что в каждой группе обрить бобров за один запуск можно. Но тогда потребуется m + 1 запусков Брабобрея-5000.

Все бобры взбалмошны, поэтому так и норовят поменяться местами. Поэтому, подходя к задаче более формально, можно рассматривать запросы двух видов:

  • какое минимальное количество запусков Брабобрея-5000 потребуется, чтобы обрить бобров с номерами от x до y включительно?
  • два бобра на позициях x и y (то есть бобры ax и ay) поменялись местами.

Можно считать, что одного и того же бобра можно обривать сколь угодно много раз.

Входные данные

В первой строке задано целое число n — общее количество бобров, 2 ≤ n. Во второй строке записаны через пробел n целых чисел — исходная перестановка бобров.

В третьей строке задано целое число q — количество запросов, 1 ≤ q ≤ 105. В последующих q строках содержатся сами запросы. Каждый запрос i имеет вид pi xi yi, где pi — вид запроса (1 — обрить бобров с xi по yi включительно, 2 — поменять местами бобров, стоящих на позициях xi и yi). Для всех запросов выполняется: 1 ≤ xi < yi ≤ n.

  • для получения 30 баллов требуется решить задачу при n ≤ 100 (подзадача B1);
  • для получения 100 баллов требуется решить задачу при n ≤ 3·105 (подзадачи B1+B2).

Обратите внимание, что количество запросов q и в подзадаче B1, и в подзадаче B2 ограничено 1 ≤ q ≤ 105.

Выходные данные

Для каждого запроса с pi = 1 выведите минимальное количество запусков Брабобрея-5000.

Примеры
Входные данные
5
1 3 4 2 5
6
1 1 5
1 3 4
2 2 3
1 1 5
2 1 5
1 1 5
Выходные данные
2
1
3
5