CF331B2.Shave Beaver!

The Smart Beaver has recently designed and built an innovative nanotechnologic all-purpose beaver mass shaving machine, "Beavershave 5000". Beavershave 5000 can shave beavers by families! How does it work? Very easily!

There are n beavers, each of them has a unique id from 1 to n. Consider a permutation _a_1, _a_2, ..., a__n of n these beavers. Beavershave 5000 needs one session to shave beavers with ids from x to y (inclusive) if and only if there are such indices _i_1 < _i_2 < ... < i__k, that _a__i_1 = x, _a__i_2 = x + 1, ..., a__i__k - 1 = y - 1, a__i__k = y. And that is really convenient. For example, it needs one session to shave a permutation of beavers 1, 2, 3, ..., n.

If we can't shave beavers from x to y in one session, then we can split these beavers into groups [x, _p_1], [_p_1 + 1, _p_2], ..., [p__m + 1, y] (x ≤ _p_1 < _p_2 < ... < p__m < y), in such a way that the machine can shave beavers in each group in one session. But then Beavershave 5000 needs m + 1 working sessions to shave beavers from x to y.

All beavers are restless and they keep trying to swap. So if we consider the problem more formally, we can consider queries of two types:

• what is the minimum number of sessions that Beavershave 5000 needs to shave beavers with ids from x to y, inclusive?
• two beavers on positions x and y (the beavers a__x and a__y) swapped.

You can assume that any beaver can be shaved any number of times.

聪明的海狸最近设计并制造了一台创新的纳米技术通用海狸群体剃毛机——“海狸剃刀5000”。海狸剃刀5000能够按家族为单位对海狸进行剃毛！它的工作原理非常简单！

共有 $n$ 只海狸，每只海狸拥有一个从 $1$ 到 $n$ 的唯一编号。考虑这 $n$ 只海狸的一个排列 $a_1,\,a_2,\,\dots,\,a_n$。当且仅当存在下标序列 $i_1 < i_2 < \dots < i_k$，使得 $a_{i_1} = x$，$a_{i_2} = x+1$，…，$a_{i_{k-1}} = y-1$，$a_{i_k} = y$ 时，海狸剃刀5000只需一个工作会话即可剃除编号在区间 $[x,\,y]$（含端点）内的所有海狸。这确实十分便捷。例如，对于排列 $1,\,2,\,3,\,\dots,\,n$，只需一个会话即可完成全部剃毛。

若无法在单个会话中剃除编号从 $x$ 到 $y$ 的所有海狸，则可将这些海狸划分为若干连续子区间：$[x,\,p_1],\,[p_1+1,\,p_2],\,\dots,\,[p_m+1,\,y]$（其中 $x \le p_1 < p_2 < \dots < p_m < y$），使得机器可在每个子区间内分别用一个会话完成剃毛。此时，海狸剃刀5000总共需要 $m+1$ 个工作会话来剃除编号在 $[x,\,y]$ 内的所有海狸。

所有海狸都坐立不安，不断尝试相互交换位置。因此，若更形式化地建模该问题，我们需支持两类查询：

• 海狸剃刀5000 剃除编号在区间 $[x,\,y]$（含端点）内的所有海狸所需的最少会话数是多少？
• 位置 $x$ 与位置 $y$ 上的两只海狸（即海狸 $a_x$ 和 $a_y$）发生交换。

你可以假设任意一只海狸可被重复剃毛任意多次。

The first line contains integer n — the total number of beavers, 2 ≤ n. The second line contains n space-separated integers — the initial beaver permutation.

The third line contains integer q — the number of queries, 1 ≤ q ≤ 105. The next q lines contain the queries. Each query i looks as p__i x__i y__i, where p__i is the query type (1 is to shave beavers from x__i to y__i, inclusive, 2 is to swap beavers on positions x__i and y__i). All queries meet the condition: 1 ≤ x__i < y__i ≤ n.

• to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem B1);
• to get 100 points, you need to solve the problem with constraints: n ≤ 3·105 (subproblems B1+B2).

Note that the number of queries q is limited 1 ≤ q ≤ 105 in both subproblem B1 and subproblem B2.

第一行包含一个整数 $n$ —— 河狸的总数，满足 $2 \leq n$。第二行包含 $n$ 个以空格分隔的整数 —— 初始的河狸排列。

第三行包含一个整数 $q$ —— 查询次数，满足 $1 \leq q \leq 10^5$。接下来的 $q$ 行为各次查询。第 $i$ 次查询的形式为 $p_i\ x_i\ y_i$，其中 $p_i$ 表示查询类型（$1$ 表示剃除位置从 $x_i$ 到 $y_i$（含端点）的所有河狸；$2$ 表示交换位于位置 $x_i$ 和 $y_i$ 的两只河狸）。所有查询均满足条件：$1 \leq x_i < y_i \leq n$。

• 若要获得 30 分，需在约束条件 $n \leq 100$ 下解决该问题（子问题 B1）；
• 若要获得 100 分，需在约束条件 $n \leq 3 \cdot 10^5$ 下解决该问题（子问题 B1 + B2）。

注意：在子问题 B1 和子问题 B2 中，查询次数 $q$ 的限制均为 $1 \leq q \leq 10^5$。

For each query with p__i = 1, print the minimum number of Beavershave 5000 sessions.

对于每个满足 $p_i = 1$ 的查询，输出 Beavershave 5000 所需的最少会话次数。