ボゾソート

　

ボゾソートはボゴソートと並んで極めて効率の悪い整列アルゴリズムである。ボゾソートは乱数に基づくアルゴリズムで、以下の手順で数列の要素を整列する：

1. ２つの要素をランダムに選び、交換する。
2. 全ての要素が昇順に整列されているか確認する。
3. 整列されていれば終了。そうでなければ1.へ戻る。

あなたはボゾソートを解析するために、あらかじめいくつか用意された２つの要素の位置にしたがって、シミュレーションすることにした。

整数の数列に対して２つの要素を交換する命令がいくつか与えられる。何回目の命令で数列が昇順になるかを求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$a_1$ $a_2$ ... $a_N$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_Q$ $y_Q$

１行目に数列の要素数$N$ ($2 \leq N \leq 300,000$)が与えられる。続く１行に、数列の各要素を表す整数$a_i$ ($1 \leq a_i \leq 10^9$)が与えられる。３行目に命令の個数$Q$ ($1 \leq Q \leq 300,000$)が与えられる。続く$Q$行に$i$番目の命令を表す２つの整数$x_i,y_i$ ($1 \leq x_i,y_i \leq N$)が与えられる。命令は数列の$x_i$番目の要素と$y_i$番目の要素を交換することを示す。ただし、$x_i \ne y_i$である。

出力

最初に数列が昇順になる命令の番号を1行に出力する。ただし、最初から昇順に整列されている場合は0、全ての命令を処理しても昇順にできない場合は-1を出力する。

入出力例

入力例１

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

Note

Algorithm

 

---