Election Queries

문제

Farmer John has $NN$ ($2\le N\le 2\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\; \backslash cdot\; 10^5$) cows numbered from $11$ to $NN$. An election is being held in FJ's farm to determine the two new head cows in his farm. Initially, it is known that cow $ii$ will vote for cow $a_{i}a\_i$ ($1\le a_i\le N1\; \backslash leq\; a\_i\; \backslash leq\; N$).

To determine the two head cows, FJ will hold his election in the following process:

• Choose an arbitrary subset $SS$ of his cows that contains at least one cow but not all cows. FJ is able to choose cow $xx$ as the first head cow if its votes appear most frequently among all votes cast by cows in $SS$.
• FJ is able to choose cow $yy$ as the second head cow if its votes appear most frequently among votes cast by cows not in $SS$.
• For a fixed subset $SS$, FJ denotes the diversity between his head cows as $\mathrm{\mid }x-y\mathrm{\mid }|x\; -\; y|$. As FJ does not like having leaders with similar numbers, he wants to choose $SS$ such that the diversity is maximized. Note that if FJ is not able to choose two distinct head cows, then the diversity is $00$.

However, some cows keep changing their minds, and FJ may have to rerun the election many times! Therefore, he asks you $QQ$ ($1\le Q\le {10}^{5}1\; \backslash leq\; Q\; \backslash leq\; 10^5$) queries. In each query, a cow changes their vote. After each query, he asks you for the maximum possible diversity among his new head cows.

입력

The first line contains $NN$ and $QQ$.

The following line contains $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash ldots,\; a\_N$.

The following $QQ$ lines contain two integers $ii$ and $xx$, representing the update $a_i=xa\_i\; =\; x$ ($1\le i,x\le N1\; \backslash leq\; i,\; x\; \backslash leq\; N$).

출력

Output $QQ$ lines, the $ii$'th of which is the maximum possible diversity after the first $ii$ queries.

5 3
1 2 3 4 5
3 4
1 2
5 2

4
3
2

8 5
8 1 4 2 5 4 2 3
7 4
8 4
4 1
5 8
8 4

4
4
4
7
7