Hello again Codeforces community!

I'm back with another problem, which I'm not able to solve. I don't have any link, it isn't from any site.

You are given a permutation of size N and Q queries. In 1 query, you are given x and y, and you need to swap the values on position x and y (formally, you need to swap v[x] and v[y]). After every query, you have to print the number of prefixes of the permutation, that are permutations.

For example, if you have array A = [2, 1, 3, 4], the answer is 3 (permutation at index 2, 3 and 4).

Example:

Input:
4 3
1 4 3 2
2 3
2 4 1 2

Output:

2 3 2

1 <= N, Q <= 100000.

The only approach I could come up with was brute force. Could anyone help me?