Farmer John's Leader Cows Election

Farmer John has \(N\) cows (\(2\le N \le 2\cdot10^5\)) numbered from \(1\) to \(N\). An election is held to choose two new leader cows. Initially, for each cow \(i\) the vote is cast to cow \(a_i\) (where \(1\le a_i\le N\)).

The election proceeds as follows:

1. Farmer John chooses an arbitrary non-empty proper subset \(S\) (i.e. \(S\neq \emptyset\) and \(S\neq \{1,2,\dots,N\}\)).
2. Within \(S\), the candidate that receives the most votes is selected as the first leader \(x\).
3. Within the complement set \(\overline{S}\), the candidate that receives the most votes is selected as the second leader \(y\).
4. The "difference" between the two leaders is defined as \(|x-y|\). If it is impossible to choose two different leaders, the difference is \(0\).

Farmer John will perform \(Q\) queries (\(1\le Q\le 10^5\)); in each query, one cow changes its vote to a new candidate. After each update, you need to determine the maximum difference that can possibly be achieved by an appropriate choice of \(S\).

Note: The time limit for this problem is 3 seconds, which is 1.5 times the default.

inputFormat

The first line contains two integers \(N\) and \(Q\) (the number of cows and the number of queries).

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\) where \(a_i\) indicates the candidate that cow \(i\) votes for initially.

Each of the next \(Q\) lines contains two integers \(i\) and \(v\), meaning that cow \(i\)'s vote is changed to candidate \(v\).

outputFormat

For each query, output the maximum difference \(|x-y|\) that can be achieved after the vote update, on a separate line.

sample

3 2
1 2 3
1 3
2 1

1
2