Алмастыру — бұл ұзындығы $n$ болатын, 1-ден $n$-ге дейінгі бүтін сандардың тізбегі, тізбекте барлық сандар бір реттен кездеседі. Мысалы, [1], [4,3,5,1,2], [3,2,1] — алмастырулар, ал [1,1], [4,3,1], [2,3,4] — емес.

Ұзындығы $n$ болатын $p$ алмастыруы берілген. Сізге $n-1$ операция жасауға рұқсат етіледі, олардың $i$-сы $p_i$ және $p_{i+1}$ екі көршілес элементті орын ауыстырумен алмастыруды өзгертеді. Әр $i$ деген операцияны бір реттен артық қолдануға болмайды және операцияны кез келген ретпен қолдануға болады.

Сізге $q$ сұрау берілген. Әр сұрауда $p_x$ және $p_y$ екі элемент орын ауыстырылады. Бастапқы алмастыру үшін және әр сұраудан кейін қазіргі алмастыруды сорттау үшін қажетті рұқсат етілген операциялардың минималды санын анықтау қажет, немесе сорттау мүмкін емес болса, $-1$ шығару керек.

Енгізу

Бірінші жолда бір бүтін сан $n$ $(2\le n\le {10}^6)$ — алмастырудың ұзындығы.

Екінші жолда $n$ түрлі бүтін сандар $p_1,p_2,\dots ,p_n$ — $1$-ден $n$-ге дейінгі сандардың алмастыруы.

Үшінші жолда бір бүтін сан $q$ $(0\le q\le {10}^6)$ — сұраулар саны.

Келесі $q$ жолда екі бүтін сан $x$ және $y$ $(1\le x,y\le n,x\ne y)$ — орын ауыстыру қажет элементтердің индекстері.

Шығару

$q+1$ жолды шығарыңыз, әр жолда бір сан — қазіргі алмастыруды сорттау үшін қажетті рұқсат етілген операциялардың минималды саны, немесе $-1$, егер бұл мүмкін болмаса.

Бағалау жүйесі

Бұл тапсырмада $7$ ішкі есеп бар.

Мысалдар

Енгізу 1

4
2 1 4 3
3
1 2
3 2
3 4

Жауап 1

2
1
2
-1

Ескертпелер

Бастапқы алмастыру: [2, 1, 4, 3] $p_1$ және $p_2$ орын ауыстырамыз, нәтижесінде: [1, 2, 4, 3] $p_3$ және $p_4$ орын ауыстырамыз, нәтижесінде: [1, 2, 3, 4]

Бірінші сұраудан кейін: [1, 2, 4, 3], $p_3$ және $p_4$ орын ауыстырамыз, нәтижесінде: [1, 2, 3, 4]

Екінші сұраудан кейін: [1, 4, 2, 3], $p_2$ және $p_3$ орын ауыстырамыз, нәтижесінде: [1, 2, 4, 3], $p_3$ және $p_4$ орын ауыстырамыз, нәтижесінде: [1, 2, 3, 4]

Үшінші сұраудан кейін: [1, 4, 3, 2] және бұл алмастыруны сорттау мүмкін емес.