D. Bookshelf Sorting
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ирма работает в библиотеке. Каждый день она наблюдает, как посетители берут пару книг с полки, читают их, затем ставят на те же места, откуда они их взяли, но не в том же порядке, в котором они стояли изначально. Рассмотрим одну конкретную полку, на которой стоят $$$n$$$ книг в некотором порядке, позиции книг пронумерованы слева направо числами от $$$1$$$ до $$$n$$$. Будем считать, что $$$i$$$-й посетитель берет книги на позициях $$$x_i$$$ и $$$y_i$$$, читает их, и ставит их обратно, но в неправильном порядке, то есть книга, ранее стоявшая на позиции $$$x_i$$$ теперь будет стоять на позиции $$$y_i$$$, и наоборот.

Вечером, после закрытия, Ирма хочет вернуть книги на свои места. Для каждой книги она знает число $$$p_i$$$ — позицию, на которой книга должна стоять в конечном итоге. Для того, чтобы поставить книги в желаемом порядке, Ирма может вытащить любую книгу, и поставить ее либо в начало, либо в конец полки (на первую или последнюю позицию соответственно).

Какое минимальное число таких действий нужно совершить Ирме, чтобы упорядочить книги? Ответьте на этот вопрос для некоторого начального расположения книг, заданного числами $$$p_i$$$, а также после каждого посетителя, который поменял некоторые две книги местами.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le q \le 2 \cdot 10^5$$$) — количество книг на полке и количество посетителей. Следующая строка содержит $$$n$$$ различных целых чисел $$$p_i$$$ ($$$1 \le p_i \le n$$$), означающие, что книга на $$$i$$$-й позиции должна оказаться на позиции $$$p_i$$$.

Следующие $$$q$$$ строк описывают действия посетителей. Каждая строка содержит пару целых чисел $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i \lt y_i \le n$$$), и означает то, что $$$i$$$-й посетитель поменял местами книги на позициях $$$x_i$$$ и $$$y_i$$$.

Выходные данные

Выведите $$$q + 1$$$ целое число — минимальное количество действий, необходимое для того, чтобы упорядочить все книги на полке для изначальной расстановки, после первого посетителя, ..., после всех $$$q$$$ посетителей.

Система оценки
{Баллы}{Ограничения}
110$$$n, q \le 8$$$
215$$$n, q \le 200$$$
315$$$n \le 2000$$$; $$$q = 0$$$
415$$$n, q \le 2000$$$
520$$$n \le 2 \cdot 10^5$$$; $$$q = 0$$$
625$$$n, q \le 2 \cdot 10^5$$$
Пример
Входные данные
5 2
5 1 2 4 3
4 5
1 4
Выходные данные
2
1
3
Примечание

Изначально книги стоят в порядке $$$(5, 1, 2, 4, 3)$$$. Для того, чтобы поставить книги на свои места, нужно сначала вытащить книгу с номером $$$4$$$ и поставить ее в конец. Затем сделать то же самое с книгой $$$5$$$. После первого изменения порядок выглядит как $$$(5, 1, 2, 3, 4)$$$; здесь достаточно книгу $$$5$$$ поставить на последнее место. После второго изменения порядок книг становится $$$(3, 1, 2, 5, 4)$$$. В этом случае минимальное количество действия равно $$$3$$$, существует несколько способов добиться верного порядка за $$$3$$$ действия.