CF331B1.Shave Beaver!

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<=10^{5}$ . 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·10^{5}$ (subproblems B1+B2).

Note that the number of queries $q$ is limited $1<=q<=10^{5}$ in both subproblem B1 and subproblem B2.

For each query with $p_{i}=1$ , print the minimum number of Beavershave 5000 sessions.

无