006 - ボゾソート

問題文

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

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

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

課題

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

入力・出力

入力

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

N
a1 a2 … aN
Q
x1 y2
x1 y2
:
xQ yQ

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

出力

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

入出力例

入力例 1

6
9 7 5 6 3 1
3
1 6
2 5
3 4

出力例 1

2

---

入力例 2

4
4 3 2 1
2
1 2
3 4

出力例 2

-1

---

入力例 3

5
1 1 1 2 2
1
1 2

出力例 3

0