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;

public class HackerRank {
	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;
			}

		}

	}
}
