Problems
Farmer John has N cows numbered from 1 to N (2 ≤ N ≤ 2·10^5). An election is being held on his farm to determine the two new head cows. Initially, it is known that cow i will vote for cow a_i (1 ≤ a_i ≤ N).
To determine the two head cows, Farmer John will hold his election as follows:
Choose an arbitrary subset S of his cows that contains at least one cow but not all cows.
Among the cows in S, he is able to choose cow x as the first head cow if its votes appear most frequently among the votes cast by cows in S.
Among the cows not in S, he is able to choose cow y as the second head cow if its votes appear most frequently among the votes cast by cows not in S.
For a fixed subset S, the diversity between his head cows is defined as |x - y|. If Farmer John is not able to choose two distinct head cows, then the diversity is 0.
However, some cows keep changing their minds, so there are Q queries (1 ≤ Q ≤ 10^5). In each query, a cow changes her vote (i.e., update a_i = x). After each query, Farmer John asks you to determine the maximum possible diversity among his head cows.
Input
The first line contains two integers N and Q.
The following line contains N space-separated integers a_1, a_2, …, a_N.
The following Q lines each contain two integers i and x, representing an update (a_i = x).
Output
Output Q lines, where the i-th line is the maximum possible diversity after processing the first i updates. (If it is impossible to choose two distinct head cows for some subset S, the diversity for that S is 0.)
Example #1
5 3
1 2 3 4 5
3 4
1 2
5 2
4
3
2
After the first query, the vote array becomes [1, 2, 4, 4, 5]. By choosing an appropriate subset S, for example S = {1, 3}, the majority vote among S can be made to be 1 (or 4) and the majority vote among the remaining cows can be made to be 5, yielding a diversity of |1 - 5| = 4.
After the second query, the vote array becomes [2, 2, 4, 4, 5]. With a suitable choice of S (e.g., S = {4, 5}), the maximum diversity achievable is 3.
After the third query, the vote array becomes [2, 2, 4, 4, 2]. Now, the distinct vote values are only 2 and 4, so the maximum diversity is |2 - 4| = 2.
Example #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
You must sign in to write code.