Алмастыруды минималды сорттау
Алмастыру — бұл ұзындығы \(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 \leq n \leq 10^6)\) — алмастырудың ұзындығы.
Екінші жолда \(n\) түрлі бүтін сандар \(p_1, p_2, \dots, p_n\) — \(1\)-ден \(n\)-ге дейінгі сандардың алмастыруы.
Үшінші жолда бір бүтін сан \(q\) \((0 \leq q \leq 10^6)\) — сұраулар саны.
Келесі \(q\) жолда екі бүтін сан \(x\) және \(y\) \((1 \leq x, y \leq n, x \neq y)\) — орын ауыстыру қажет элементтердің индекстері.
Шығару
\(q+1\) жолды шығарыңыз, әр жолда бір сан — қазіргі алмастыруды сорттау үшін қажетті рұқсат етілген операциялардың минималды саны, немесе \(-1\), егер бұл мүмкін болмаса.
Бағалау жүйесі
Бұл тапсырмада \(7\) ішкі есеп бар.
| Ішкі есеп | Қосымша шектеулер | Ұпайлар |
|---|---|---|
| \(0\) | Мысалдар | \(0\) |
| \(1\) | \(n=3, q = 0\) | \(5\) |
| \(2\) | \(n \leq 9\), \(q \leq 10\) | \(11\) |
| \(3\) | Барлық \(i\) үшін \(p_i=i\). Сонымен қатар барлық \(x_1, x_2, ..., x_q, y_1, y_2, ..., y_q\) сандар әртүрлі | \(17\) |
| \(4\) | \(n, q \leq 500\) | \(9\) |
| \(5\) | \(n, q \leq 10000\) | \(12\) |
| \(6\) | \(n, q \leq 200000\) | \(20\) |
| \(7\) | — | \(26\) |
Мысалдар
Енгізу 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] және бұл алмастыруны сорттау мүмкін емес.
Пікірлер