Johnny has a new toy. As you may guess, it is a little bit extraordinary. The toy is a permutation P of numbers from 1 to n, written in one row next to each other. 

For each i from 1 to n - 1 between P_i and P_{i + 1} there is a weight W_i written, and those weights form a permutation of numbers from 1 to n - 1. There are also extra weights W_0 = W_n = 0.

The instruction defines subsegment [L, R] as good if W_{L - 1} < W_i and W_R < W_i for any i in \\{L, L + 1, …, R - 1\}. For such subsegment it also defines W_M as minimum of set \\{W_L, W_{L + 1}, …, W_{R - 1}\}. 

Now the fun begins. In one move, the player can choose one of the good subsegments, cut it into [L, M] and [M + 1, R] and swap the two parts. More precisely, before one move the chosen subsegment of our toy looks like: $$$W_{L - 1}, P_L, W_L, …, W_{M - 1}, P_M, W_M, P_{M + 1}, W_{M + 1}, …, W_{R - 1}, P_R, W_R and afterwards it looks like this: W_{L - 1}, P_{M + 1}, W_{M + 1}, …, W_{R - 1}, P_R, W_M, P_L, W_L, …, W_{M - 1}, P_M, W_R Such a move can be performed multiple times (possibly zero), and the goal is to achieve the minimum number of inversions in P$$$. 

Johnny's younger sister Megan thinks that the rules are too complicated, so she wants to test her brother by choosing some pair of indices X and Y, and swapping P_X and P_Y (X might be equal Y). After each sister's swap, Johnny wonders, what is the minimal number of inversions that he can achieve, starting with current P and making legal moves?

You can assume that the input is generated randomly. P and W were chosen independently and equiprobably over all permutations; also, Megan's requests were chosen independently and equiprobably over all pairs of indices.

Input

The first line contains single integer n (2 ≤ n ≤ 2 ⋅ 10^5) denoting the length of the toy.

The second line contains n distinct integers P_1, P_2, …, P_n (1 ≤ P_i ≤ n) denoting the initial permutation P. The third line contains n - 1 distinct integers W_1, W_2, …, W_{n - 1} (1 ≤ W_i ≤ n - 1) denoting the weights.

The fourth line contains single integer q (1 ≤ q ≤ 5 ⋅ 10^4) — the number of Megan's swaps. The following q lines contain two integers X and Y (1 ≤ X, Y ≤ n) — the indices of elements of P to swap. The queries aren't independent; after each of them, the permutation is changed.

Output

Output q lines. The i-th line should contain exactly one integer — the minimum number of inversions in permutation, which can be obtained by starting with the P after first i queries and making moves described in the game's instruction.

Examples

Input


3
3 2 1
2 1
3
1 3
3 2
3 1


Output


0
1
0


Input


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


Output


3
1
2
1
2
3
3

Note

Consider the first sample. After the first query, P is sorted, so we already achieved a permutation with no inversions. 

After the second query, P is equal to [1, 3, 2], it has one inversion, it can be proven that it is impossible to achieve 0 inversions. 

In the end, P is equal to [2, 3, 1]; we can make a move on the whole permutation, as it is a good subsegment itself, which results in P equal to [1, 2, 3], which has 0 inversions.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Random;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author lewin
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        IJohnnyAndNewToy solver = new IJohnnyAndNewToy();
        solver.solve(1, in, out);
        out.close();
    }

    static class IJohnnyAndNewToy {
        int n;
        int[] p;
        int[] w;
        IJohnnyAndNewToy.Tree[] leaf;
        int lidx;
        long ans = 0;

        public IJohnnyAndNewToy.Tree create(int start, int end) {
            if (start + 1 == end) {
                leaf[lidx] = new IJohnnyAndNewToy.Tree();
                leaf[lidx].vals = new TreapBST.Treap(p[start]);
                leaf[lidx].count = 0;
                leaf[lidx].size = 1;
                return leaf[lidx++];
            }
            int mn = start + 1;
            for (int i = start + 1; i < end; i++) {
                if (w[i] < w[mn]) mn = i;
            }
            IJohnnyAndNewToy.Tree cur = new IJohnnyAndNewToy.Tree();
            cur.left = create(start, mn);
            cur.right = create(mn, end);
            cur.left.par = cur;
            cur.left.side = 0;
            cur.right.par = cur;
            cur.right.side = 1;
            cur.size = cur.left.size + cur.right.size;
            cur.a1 = 0;
            cur.a2 = 0;
            for (int i = start; i < mn; i++) {
                int c1 = TreapBST.rank(cur.right.vals, p[i]);
                cur.a1 += c1;
                cur.a2 += cur.right.size - c1;
            }
            cur.count = Math.min(cur.a1, cur.a2);
            ans += cur.count;
            cur.vals = null;
            for (int i = start; i < end; i++) {
                cur.vals = TreapBST.insert(cur.vals, p[i]);
            }
            return cur;
        }

        void remove(IJohnnyAndNewToy.Tree cur, int value) {
            cur.vals = TreapBST.remove(cur.vals, value);
            cur.size--;
            int side = cur.side;
            cur = cur.par;
            while (cur != null) {
                if (side == 0) {
                    int c = TreapBST.rank(cur.right.vals, value);
                    cur.a1 -= c;
                    cur.a2 -= cur.right.size - c;
                } else {
                    int c = TreapBST.rank(cur.left.vals, value);
                    cur.a2 -= c;
                    cur.a1 -= cur.left.size - c;
                }
                ans -= cur.count;
                cur.count = Math.min(cur.a1, cur.a2);
                ans += cur.count;

                cur.size--;
                cur.vals = TreapBST.remove(cur.vals, value);
                side = cur.side;
                cur = cur.par;
            }
        }

        void add(IJohnnyAndNewToy.Tree cur, int value) {
            cur.vals = TreapBST.insert(cur.vals, value);
            cur.size++;
            int side = cur.side;
            cur = cur.par;
            while (cur != null) {
                if (side == 0) {
                    int c = TreapBST.rank(cur.right.vals, value);
                    cur.a1 += c;
                    cur.a2 += cur.right.size - c;
                } else {
                    int c = TreapBST.rank(cur.left.vals, value);
                    cur.a2 += c;
                    cur.a1 += cur.left.size - c;
                }
                ans -= cur.count;
                cur.count = Math.min(cur.a1, cur.a2);
                ans += cur.count;

                cur.size++;
                cur.vals = TreapBST.insert(cur.vals, value);
                side = cur.side;
                cur = cur.par;
            }
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.nextInt();
            p = in.readIntArrayAndDecrementOne(n);
            w = new int[n + 1];
            for (int i = 1; i < n; i++) w[i] = in.nextInt() - 1;
            leaf = new IJohnnyAndNewToy.Tree[n];
            lidx = 0;
            create(0, n);
            int q = in.nextInt();
            while (q-- > 0) {
                int x = in.nextInt() - 1, y = in.nextInt() - 1;
                if (x != y) {
                    remove(leaf[x], p[x]);
                    remove(leaf[y], p[y]);
                    add(leaf[x], p[y]);
                    add(leaf[y], p[x]);
                    int t = p[x];
                    p[x] = p[y];
                    p[y] = t;
                }
                out.println(ans);
            }
        }

        static class Tree {
            public IJohnnyAndNewToy.Tree left;
            public IJohnnyAndNewToy.Tree right;
            public IJohnnyAndNewToy.Tree par;
            public int side;
            public TreapBST.Treap vals;
            public long count;
            public long a1;
            public long a2;
            public int size;

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int[] readIntArrayAndDecrementOne(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt() - 1;
            }
            return ret;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }

    static class TreapBST {
        static Random random = new Random();

        public static int getSize(TreapBST.Treap root) {
            return root == null ? 0 : root.size;
        }

        public static TreapBST.TreapPair split(TreapBST.Treap root, int minRight) {
            if (root == null)
                return new TreapBST.TreapPair(null, null);
            root.update();
            if (root.key >= minRight) {
                TreapBST.TreapPair leftSplit = split(root.left, minRight);
                root.left = leftSplit.right;
                root.update();
                leftSplit.right = root;
                return leftSplit;
            } else {
                TreapBST.TreapPair rightSplit = split(root.right, minRight);
                root.right = rightSplit.left;
                root.update();
                rightSplit.left = root;
                return rightSplit;
            }
        }

        public static TreapBST.Treap merge(TreapBST.Treap left, TreapBST.Treap right) {
            if (left != null) left.update();
            if (right != null) right.update();
            if (left == null)
                return right;
            if (right == null)
                return left;
            // if (random.nextInt(left.size + right.size) < left.size) {
            if (left.prio > right.prio) {
                left.right = merge(left.right, right);
                left.update();
                return left;
            } else {
                right.left = merge(left, right.left);
                right.update();
                return right;
            }
        }

        public static TreapBST.Treap insert(TreapBST.Treap root, int key) {
            TreapBST.TreapPair t = split(root, key);
            return merge(merge(t.left, new TreapBST.Treap(key)), t.right);
        }

        public static TreapBST.Treap remove(TreapBST.Treap root, int key) {
            TreapBST.TreapPair t = split(root, key);
            return merge(t.left, split(t.right, key + 1).right);
        }

        public static int rank(TreapBST.Treap root, int val) {
            if (root == null) {
                return 0;
            }
            if (root.key <= val) {
                return rank(root.right, val) + 1 + getSize(root.left);
            } else {
                return rank(root.left, val);
            }
        }

        public static class Treap {
            public int key;
            public int size;
            public long prio;
            public int lazy;
            public TreapBST.Treap left;
            public TreapBST.Treap right;

            public Treap(int key) {
                this.key = key;
                prio = random.nextLong();
                size = 1;
                lazy = 0;
            }

            public void update() {
                size = 1 + getSize(left) + getSize(right);
                if (lazy != 0) {
                    if (left != null) {
                        left.lazy += lazy;
                        left.key += lazy;
                    }
                    if (right != null) {
                        right.lazy += lazy;
                        right.key += lazy;
                    }
                    lazy = 0;
                }
            }

        }

        public static class TreapPair {
            public TreapBST.Treap left;
            public TreapBST.Treap right;

            public TreapPair(TreapBST.Treap left, TreapBST.Treap right) {
                this.left = left;
                this.right = right;
            }

        }

    }
}

