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.util.*;
import java.io.*;

public class B {
    static class Node {
        int ll;
        int rr;
        Node L;
        Node R;
        
        Integer first = null;
        Integer last = null;
        Integer pos = null;
        int cost = 0;
        
        public Node(int ll, int rr) {
            this.ll = ll;
            this.rr = rr;
            if(leaf()) {
                this.first = this.last = this.pos = A[ll];
                this.cost = 1;
            }
        }
        boolean leaf() { return ll+1==rr; }
        void fix() {
            if(leaf()) return;
            first = L.first;
            last = R.last;
            cost = L.cost + R.cost + (L.last < R.first ? -1 : 0);
        }
    }
    static Node mk_tree(int ll, int rr) {
        Node n = new Node(ll, rr);
        if(ll+1==rr) return n;
        else {
            int m = (ll+rr)/2;
            n.L = mk_tree(ll, m);
            n.R = mk_tree(m, rr);
            n.fix();
            return n;
        }
    }
    static void fast_swap(int i, int j) {
        int bi = P[i];
        int bj = P[j];
        P[i] = bj;
        P[j] = bi;
        set(bi, j);
        set(bj, i);
    }
    static void set(int i, int x) { _set(i, x, root); }
    static void _set(int i, int x, Node n) {
        if(n.leaf()) {
            n.pos = n.first = n.last = x;
        }
        else {
            int m = (n.ll+n.rr)/2;
            if(i < m) _set(i, x, n.L);
            else _set(i, x, n.R);
            n.fix();
        }
    }
    static int fast_cost(int x, int y) { return _cost(x, y+1, root); }
    static int _cost(int x, int y, Node n) {
        if(x<=n.ll && n.rr <= y) return n.cost;
        int m = (n.ll+n.rr)/2;
        if(m<=x) {
            //System.out.println("R:"+x+" "+y+" "+n.ll+" "+n.rr);
            return _cost(x,y,n.R);
        }
        else if(y<=m) {
            //System.out.println("L:"+x+" "+y+" "+n.ll+" "+n.rr);
            return _cost(x, y, n.L);
        }
        else {
            //System.out.println("B:"+x+" "+y+" "+n.ll+" "+n.rr+" "+m);
            return _cost(x,y,n.L) + _cost(x,y,n.R) + (n.L.last < n.R.first ? -1 : 0);
        }
    }
    static Node root = null;
    static int[] P; //P[i] is beaver at position i
    static int[] A; //A[i] is position of beaver i

    static void swap(int i, int j) {
        int bi = P[i];
        int bj = P[j];
        P[i] = bj;
        P[j] = bi;
        A[bi] = j;
        A[bj] = i;
    }
    static int cost(int x, int y) {
        int ans = 0;
        for(int i=x; i<y; i++)
            if(A[i] > A[i+1])
                ans++;
        return ans+1;
    }

    static int i(String s) { return Integer.parseInt(s); }
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = i(in.readLine());
        String[] arr = in.readLine().split(" ");
        A = new int[n];
        P = new int[n];
        for(int i=0; i<n; i++) {
            int beaver = i(arr[i])-1;
            P[i] = beaver;
            A[beaver] = i;
        }
        root = mk_tree(0, n);

        int q = i(in.readLine());
        for(int t=0; t<q; t++) {
            arr = in.readLine().split(" ");
            int typ = i(arr[0]);
            if(typ==2) {
                int i = i(arr[1])-1;
                int j = i(arr[2])-1;
                fast_swap(i, j);
            } else if(typ==1) {
                int x = i(arr[1])-1;
                int y = i(arr[2])-1;
                System.out.println(fast_cost(x,y));
            }
        }
    }
}
