Sorting Game

Ermac and Aizan play a game with a sequence $S$ of length $N$. Each integer from 0 to $N-1$ appears exactly once in $S$. The goal of the game is to sort the sequence in ascending order. Aizan tries to sort it, and Ermac tries to keep it unsorted for as long as possible when that cannot be avoided.

In one game, each round Ermac picks two numbers and swaps their positions, and then Aizan picks two numbers and swaps their positions. Both Ermac and Aizan may pick the same number twice so that nothing moves. If the sequence is sorted in ascending order at the end of a round, the game ends. If the sequence is already sorted at the start, the number of rounds needed is 0.

To play several games, Ermac and Aizan modify $S$ $M$ times and play a game after each change. Two arrays $X$ and $Y$ of length $M$ are given. Games are numbered from 0 to $M-1$ in the order they are played. Before game $i$ starts, the numbers at positions $X_i$ and $Y_i$ of the sequence from the moment game $i-1$ started are swapped, and game $i$ is played on the resulting sequence. The sequence at the moment game $-1$ started is defined as $S$.

For each game, determine whether Aizan is guaranteed to sort the sequence after some number of rounds. If so, find the minimum number of rounds needed.

The first line contains $N$ ($1 \le N \le 2 \times 10^5$).

The second line contains the $N$ numbers of the sequence $S$, separated by spaces.

The third line contains $M$ ($1 \le M \le 6 \times 10^5$).

Each of the next $M$ lines contains $X_i$ and $Y_i$, separated by a space ($0 \le X_i, Y_i < N$).

For each of the $M$ games, in the order the games are played, print $-1$ if the game can continue indefinitely. Otherwise, print the minimum number of rounds needed. Separate the values with spaces.