Bookshelf Sorting

Irma works in a library. Every day she watches visitors take a couple of books from the bookshelf, read them, and put the books back in the same places they took them from. Usually people mess up the order and swap the two books they read. Let's look at one specific bookshelf with $n$ books in some order, numbered from $1$ to $n$ from left to right. The $i$-th visitor takes the books from positions $x\_i$ and $y\_i$ and puts them back in the same positions, but in the wrong order. After the $i$-th visitor, the book that was at $x\_i$ is now at position $y\_i$ and vice versa.

In the evening, after the library closes, Irma wants to put all the books back in their places. Each book has a number $p\_i$, the position where that book should end up. To rearrange books, Irma can take any book from the shelf and insert it at the beginning or at the end, so it ends up in the first or the last place on the shelf.

What is the minimum number of moves Irma can make to put all the books in order? Answer this question for the initial placement of books, determined by $p\_i$, and after each visitor that swaps the places of two books.

The first line contains two integers $n$ and $q$ ($2 \le n \le 2 \cdot 10^5$; $0 \le q \le 2 \cdot 10^5$), the number of books on the shelf and the number of visitors. The next line contains $n$ distinct integers $p\_i$ ($1 \le p\_i \le n$), meaning that the book in the $i$-th position must end up in position $p\_i$.

The next $q$ lines describe the library's visitors. Each line contains two integers $x\_i$, $y\_i$ ($1 \le x\_i < y\_i \le n$), meaning that the $i$-th visitor swapped the two books at positions $x\_i$ and $y\_i$.

Print $q + 1$ integers: the minimum number of moves required to sort all books for the initial order, then for the order after the first visitor, ..., after all $q$ visitors.

The initial order of books is $(5, 1, 2, 4, 3)$. To sort these books, first put the book $4$ at the end, then do the same with book $5$. After the first visitor, the bookshelf looks like $(5, 1, 2, 3, 4)$; it is enough to move the book $5$ to the end. After the second visitor the order of books is $(3, 1, 2, 5, 4)$. For this order the minimum number of moves is $3$, and there are several ways to reach the final order in $3$ moves.