Scorpion Test for Permutation Graphs

Think about the graphs used in computer science, and in particular about undirected graphs, whose edges carry no direction. Some undirected graphs have a special property.

• In some undirected graphs a path exists between every pair of vertices. We call such a graph a connected graph.
• In some undirected graphs there is no cycle at all. We call such a graph a forest.
• In some undirected graphs there is no cycle, and a path exists between every pair of vertices. We call such a graph a tree.
• And some undirected graphs are scorpion-like. We call such a graph a scorpion graph.

Connected graph	Forest	Tree	Scorpion graph

This problem is about scorpion graphs. A graph is scorpion-like when it satisfies the following.

• The graph is connected.
• Every vertex belongs to one of the four kinds below.
  • Sting There is exactly one sting vertex, and it is joined to the tail vertex only.
  • Tail There is exactly one tail vertex, and it is joined to the sting vertex and the body vertex only.
  • Body There is exactly one body vertex, and it is joined to the tail vertex and to every foot vertex only.
  • Foot Every vertex other than the sting, the tail, and the body is a foot vertex. Each foot vertex is joined to the body vertex, and it is joined to neither the tail vertex nor the sting vertex. Two foot vertices may be joined to each other, or they may not.

The picture above is an example of a scorpion graph.

Computer scientists found this property and gave it a name because the cost of testing it is unusual. Given an $N \times N$ adjacency matrix, deciding a nontrivial graph property (connected graph, forest, tree, and so on) normally takes $O(N^2)$ time on top of reading the input. Scorpion-ness is different. No matter how many edges the graph has, an algorithm decides it in $O(N)$ time on top of reading the input.

Jaehyun admired that property, so he hands you another unusual graph, the permutation graph, and asks whether it is scorpion-like. The permutation graph of a permutation $A_1, A_2, \dots, A_N$ of length $N$ is defined as follows.

• The graph has $N$ vertices numbered from $1$ to $N$.
• The edges are drawn by this procedure.
  1. Draw two parallel lines. Along one line write $1, 2, \dots, N$ in order, and along the other line write $A_1, A_2, \dots, A_N$ in order.
  2. Join each pair of equal numbers with a segment.
  3. For every pair $(i, j)$ whose two segments cross, join vertex $i$ and vertex $j$ with an undirected edge.

The picture above is the permutation graph of $A = [2, 5, 4, 1, 3]$.

Jaehyun wanted a harder problem, so he added $Q$ operations that swap two elements of the permutation. Decide, after each swap, whether the permutation graph of the current $A$ is a scorpion graph. A swap is not temporary, and it stays in effect for the operations that follow.

The first line contains the length of the permutation, $N$ ($4 \le N \le 100000$).

The second line contains $N$ distinct positive integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le N$) that form the permutation $A$.

The third line contains the number of swap operations, $Q$ ($1 \le Q \le 100000$).

Each of the next $Q$ lines describes one swap operation. A line holds two positive integers $x$ and $y$ ($1 \le x, y \le N$, $x \ne y$) separated by a space. Swap the $x$-th element $A_x$ and the $y$-th element $A_y$ of the permutation $A$ first, then decide whether the permutation graph of the resulting $A$ is a scorpion graph and print the answer.

For each swap operation, print YES if the permutation graph of $A$ after the swap is a scorpion graph, and NO otherwise, one answer per line.