Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B2. Shave Beaver!

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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*_{i1} = *x*, *a*_{i2} = *x* + 1, ..., *a*_{ik - 1} = *y* - 1, *a*_{ik} = *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.

Input

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.

Output

For each query with *p*_{i} = 1, print the minimum number of Beavershave 5000 sessions.

Examples

Input

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

Output

2

1

3

5

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 16:22:45 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|