Bozosort, as well as Bogosort, is a very inefficient sort algorithm. It is a random number-based algorithm that sorts sequence elements following the steps as below:
To analyze Bozosort, you have decided to simulate the process using several predetermined pairs of elements.
You are given several commands to swap two elements. Make a program to evaluate how many times you have to run the command before the sequence is aligned in increasing order.
The input is given in the following format.
$N$ $a_1$ $a_2$ ... $a_N$ $Q$ $x_1$ $y_1$ $x_2$ $y_2$ $...$ $x_Q$ $y_Q$
The first line provides the number of sequence elements $N$ ($2 \leq N \leq 300,000$). The second line provides an array of integers $a_i$ ($1 \leq a_i \leq 10^9$) that constitutes the sequence. Each of the subsequent $Q$ lines provides a pair of integers $x_i,y_i$ ($1 \leq x_i,y_i \leq N$) that represent the $i$-th command, which swaps the two elements indicated by $x_i$ and $y_i$ ($x_i \ne y_i$).
If neat alignment in increasing order is realized the first time after execution of multiple commands, output at what time it was. Output 0 if the initial sequence is aligned in increasing order, and -1 if exhaustive execution still failed to attain the goal.
6 9 7 5 6 3 1 3 1 6 2 5 3 4
2
4 4 3 2 1 2 1 2 3 4
-1
5 1 1 1 2 2 1 1 2
0