331_B2. Shave Beaver!_10274
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 a1, a2, ..., an 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 i1 < i2 < ... < ik, that ai1 = x, ai2 = x + 1, ..., aik - 1 = y - 1, aik = 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, p1], [p1 + 1, p2], ..., [pm + 1, y] (x ≤ p1 < p2 < ... < pm < 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 ax and ay) 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 ≤ 105. The next q lines contain the queries. Each query i looks as pi xi yi, where pi is the query type (1 is to shave beavers from xi to yi, inclusive, 2 is to swap beavers on positions xi and yi). All queries meet the condition: 1 ≤ xi < yi ≤ 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.

Output

For each query with pi = 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
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {

    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

    String next() {
        while( in==null || !in.hasMoreTokens() )
            try {
                in = new StringTokenizer( br.readLine() );
            } catch (IOException e) {
                MLE();
            }
        return in.nextToken();
    }

    int nextInt(){
        return Integer.parseInt( next() );
    }

    long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

//    double nextDouble() throws IOException {
//        return Double.parseDouble(next());
//    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    void run() throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        try{
            if( oj ){
                br  = new BufferedReader(new InputStreamReader(System.in  ) );
                out = new PrintWriter(   new OutputStreamWriter(System.out) );
            } else{
                br  = new BufferedReader(new FileReader("INPUT.TXT"));
                out = new PrintWriter(   new FileWriter("OUTPUT.TXT") );
            }
        } catch (IOException e) {
            MLE();
        }
        solve();
//        deb();
        out.flush();
    }

    void MLE(){
//        for(;;);
        int[][] adj = new int[1024*1024][];
        for( int i = 0; i < adj.length; ++i )
            adj[i] = new int[1024*1024];
    }


    int n;
    int[] a, ind, tree;

    void set( int pos, int val,   int v, int tl, int tr ){
        if( tl == tr && pos == tl )
            tree[v] = val;
        else{
            int tm = (tl + tr)/2;
            if( pos <= tm )
                set( pos, val,    2*v  , tl  , tm );
            else
                set( pos, val,    2*v+1, tm+1, tr );
            tree[v] = tree[2*v] + tree[2*v+1];
        }
    }

    int sum( int l, int r,   int v, int tl, int tr ){
        if( l > r ) return 0;
        if( l==tl && r==tr ) return tree[v];
        int tm = (tl + tr)/2;
        return sum( l          , min(r,tm), 2*v  , tl  , tm ) +
               sum( max(l,tm+1), r        , 2*v+1, tm+1, tr );
    }

    int sum( int l, int r ){
        return sum( l, r,  1,1,n );
    }

    void set( int pos, int val ){
        set( pos, val,   1,1,n );
    }

    void f( int l ){
        if( 1 <= a[l] - 1 )upd( a[l] - 1 );
        upd( a[l]     );
        if( a[l] + 1 <= n ) upd( a[l] + 1 );
    }

    void upd( int a ){
        set( a, (a==n||ind[a+1]<ind[a])? 1 : 0 );
    }

    Random rnd = new Random();

    void solve(){
        long tBeg = System.currentTimeMillis();
        n = nextInt();
//        n = (int)1e5;
        a   = new int[n+1];
        ind = new int[n+1];

        for( int i = 1; i <= n; ++i ){
            int aa = nextInt();
            a  [i ] = aa;
            ind[aa] = i ;
        }
//        for( int i = 1; i <= n; ++i ){
//            a[i] = i;
//            ind[i] = i;
//        }

        int q = nextInt();
//        int q = (int)1e5;
        tree = new int[4*(n+1)];
        for( int a = 1; a <= n; ++a )
            upd( a );


        deb();
        for( int it = 0; it < q; ++it ){
            int op = nextInt();
//            int op = 1;
            if( op == 1 ){
                int al = nextInt();
                int ar = nextInt();
//                int al = rnd.nextInt(n)+1;
//                int ar = rnd.nextInt(n)+1;
//                if( al > ar ){ int t = al; al = ar; ar = t; }
                int ans = sum( al, ar );
                if( sum(ar,ar)==0 ) ++ans;
                out.println(ans);
            }
            else if( op == 2 ){
                int l = nextInt();
                int r = nextInt();
                int t = a[l];
                a[l] = a[r];
                a[r] = t;

                ind[a[l]] = l;
                ind[a[r]] = r;

                f(l);
                f(r);
//                for( int i = 1; i <= n; ++i )out.print(" "+  a[i]  );out.println();
//                for( int i = 1; i <= n; ++i )out.print(" "+ind[i]  );out.println();
//                for( int i = 1; i <= n; ++i )out.print(" "+sum(i,i));out.println();
            }
            else MLE();
        }
//        out.println( "TIME: " + ((System.currentTimeMillis()-tBeg)/1e3) );
    }

    void deb(){
    }

}

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
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 3
1 1 5
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 1 5
1 3 4
2 2 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 3
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 5
1 1 5
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 5
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 1 3
1 1 5
2 1 3
1 2 5
 5
1 3 4 2 5
6
2 2 5
2 3 4
2 2 3
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 3
1 3 4
2 2 3
1 1 5
1 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 3
1 1 3
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 5
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
2 2 5
1 3 4
2 2 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 5
1 1 3
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 1 5
1 3 4
2 4 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 5
1 1 3
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
1 2 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 3 5
1 3 4
2 2 3
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
2 2 5
2 3 4
2 2 3
1 2 5
2 1 3
1 1 5
 5
1 3 4 2 5
6
1 3 5
2 3 4
2 2 3
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 1
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 2 4
2 1 3
1 1 5
2 1 3
1 2 5
 5
1 3 4 2 5
6
1 1 5
1 3 4
2 1 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 3
1 3 4
2 2 3
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 3
1 2 5
 5
1 3 4 2 5
6
1 1 5
1 3 4
2 2 3
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
2 1 4
2 2 3
1 1 5
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
2 1 5
2 1 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 2 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 3
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 2 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 4
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 3
1 3 4
2 2 3
1 1 4
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 5
2 1 3
1 2 3
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 3
1 1 5
2 1 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 2 5
2 1 3
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 3
1 1 3
2 2 5
2 1 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 2 1
1 1 5
2 1 5
1 2 5
 5
1 3 4 2 5
6
1 2 5
1 3 4
2 4 3
1 1 5
2 2 5
1 1 5
 5
1 3 4 2 5
6
1 2 5
2 3 4
2 2 5
1 1 5
2 1 1
2 1 5

2
1
3
5
 2
1
3
5
 2
1
3
3
 2
1
3
 2
1
 2
1
3
4
 2
1
2
 2
3
4
 2
3
3
 2
2
2
 3
3
 2
1
3
3
3
 2
1
2
5
 2
3
 2
2
3
 2
1
1
4
 2
1
2
3
 2
1
1
3
 2
2
2
3
 1
1
3
 3
4
 1
1
 2
1
1
 2
3
2
 2
1
3
2
 2
1
3
4
 2
1
2
 2
1
3
 2
3
4
 2
1
3
3
 2
1
 2
1
3
 2
1
3
 2
1
3
 2
1
 2
1
2
3
 2
1
3
4
 2
1
2
 2
1
3
 2
1
3
 2
1
 2
1
2
3
 2
1
2
3
 2
3
