#740 Most Ordinary Existence

Statement

Statement language

There are $N$ members of SCSC standing in a line. Their heights are all distinct. The height rank of the member at position $i$ from the left is $P_i$ . The shortest member has rank $1$ , and the tallest has rank $N$ .

A member currently remaining in the line is called a most ordinary member if both conditions below hold.

The absolute difference between the number of members to their left and the number to their right is at most $1$ .
The absolute difference between the number of remaining members shorter than them and the number taller than them is at most $1$ .

Repeatedly choose one most ordinary member and remove them from the line until no such member exists. Removing a member preserves the relative order of all other members. If several members satisfy the conditions, you may choose any one of them. The process also ends if the line becomes empty.

You are given $Q$ queries. Query $q$ swaps the members currently at positions $x_q$ and $y_q$ . After each query, find the maximum number of members that can be removed by the process above.

Swaps are cumulative, but the removals used to compute an answer do not change the actual line. Thus, the line always contains $N$ members when a query is performed.

Input

The input is given in the following format:

$N\ Q$ $P_1\ P_2\ \cdots\ P_N$

Output

For each query, print the maximum number of members that can be removed after that query, one answer per line in query order.

Constraints

$1 \leq N,Q \leq 200\,000$ .
$1 \leq P_i \leq N$ ().

Subtasks

#	Score	Constraints
1	12	$N,Q \leq 8$ .
2	28	$N,Q \leq 2\,000$ .
3	60	No additional constraints.

Samples

Sample 1

Input

Output

After the first query, the height ranks are $[1,3,2,4,5,6]$ . Removing the member with height rank $4$ leaves no member that can be removed.

After the second query, there is no most ordinary member. After the fourth query, the original line is restored, and all members can be removed in the order of height ranks $3, 4, 2, 5$ .