정렬하기

에르맥과 아이잔은 길이 $N$인 수열 $S$로 게임을 한다. 수열 $S$에는 0부터 $N-1$까지의 정수가 한 번씩만 등장한다. 게임의 목표는 수열을 오름차순으로 정렬하는 것이다. 아이잔은 수열을 정렬하려고 하고, 에르맥은 불가피한 경우가 아니라면 최대한 오랫동안 정렬되지 않게 하려고 한다.

한 게임에서 각 라운드마다 에르맥이 두 수를 정해 서로의 위치를 바꾸고, 이어서 아이잔이 두 수를 정해 서로의 위치를 바꾼다. 에르맥과 아이잔은 같은 수를 정해 위치가 바뀌지 않게 할 수도 있다. 해당 라운드에서 수열이 오름차순으로 정렬되면 게임은 끝난다. 처음부터 정렬되어 있으면 필요한 라운드 수는 0이다.

게임을 여러 번 하기 위해 에르맥과 아이잔은 수열 $S$를 $M$번 변형하면서 게임을 한다. 길이 $M$인 배열 $X$와 $Y$가 주어진다. 게임은 한 순서대로 0부터 $M-1$까지 번호를 붙인다. $i$번째 게임을 시작하기 전에, $i-1$번째 게임을 시작했을 때의 수열에서 $X_i$번째 위치의 수와 $Y_i$번째 위치의 수를 서로 바꾼다. 그 새 수열로 게임을 한다. $-1$번째 게임을 시작했을 때의 수열은 $S$로 정의한다.

각 게임에 대해 아이잔이 특정 라운드가 지난 후 반드시 수열을 정렬하는지 판단하고, 그렇다면 필요한 라운드 수의 최솟값을 구한다.

첫 줄에 $N$이 주어진다. ($1 \le N \le 2 \times 10^5$)

둘째 줄에 수열 $S$의 $N$개의 수가 공백으로 구분되어 주어진다.

셋째 줄에 $M$이 주어진다. ($1 \le M \le 6 \times 10^5$)

이어서 $M$개의 줄에 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. ($0 \le X_i, Y_i < N$)

$M$개의 게임에 대해 게임이 일어난 순서대로, 게임이 무한히 진행 가능하면 $-1$, 그렇지 않으면 필요한 최소 라운드 수를 공백으로 구분하여 출력한다.