Observation: Let's denote an integer $k$ as the maximum number of occurrences of any integer in array $a$. Let $cnt_i$ denote the number of times that integer $i$ occurs in $a$. We can choose $x$ and $y$ as the two head cows if and only if $cnt_x$ and $cnt_y$ are both nonzero and $cnt_x + cnt_y \geq k$.

Why? Consider an integer $z$ that occurs $k$ times in $a$ and we want to check if cows $p$ and $q$ can be the two new head cows. We can place all $a_i = p$ into set $S$ and none of $a_i = q$ into $S$. Then, we can place $cnt_p$ occurrences of $a_i = z$ into $S$, leaving $k - cnt_p$ occurrences of $a_i = z$ outside $S$. Clearly, we can choose cow $p$ as cow $x$ and if we place one more occurrence of $a_i = z$ into $S$, we cannot choose cow $p$ anymore. Now we only have to ensure there are at most $cnt_q$ occurrences of $a_i = z$ outside $S$ so that we can choose cow $q$, leaving the inequality $k - cnt_p \leq cnt_q$.

Therefore, the problem boils down to: Find two integers $p$ and $q$ such that $cnt_p$ and $cnt_q$ are both nonzero, $cnt_p + cnt_q \geq k$, and $|p - q|$ is maximized.

Subtask $2$: $N, Q \leq 3000$.

This can be solved using suffix maximums in $\mathcal{O}(NQ)$ time. For each integer $d$, if we know the maximum integer that occurs at least $d$ times, we know the other head cow must be the smallest integer that occurs at least $k - d$ times.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int calc(vector<int>& a) {
	int n = a.size();
	vector<int> cnt(n+1);
	for(int i = 0; i < n; i++) cnt[a[i]]++;
	int mode_freq = 0;
	vector<int> min_freq(n+2, INF), max_freq(n+2, -INF);
	for(int i = 1; i <= n; i++){
		if(cnt[i] == 0) continue;
		mode_freq = max(mode_freq, cnt[i]);
		min_freq[cnt[i]] = min(min_freq[cnt[i]], i);
		max_freq[cnt[i]] = max(max_freq[cnt[i]], i);
	}
	for(int i = n; i >= 0; i--){
		max_freq[i] = max(max_freq[i], max_freq[i+1]);
	}
	int ans = 0;
	for(int i = 1; i <= mode_freq; i++){
		if(min_freq[i] != INF && max_freq[mode_freq - i] != -INF) {
			ans = max(ans, abs(max_freq[mode_freq - i] - min_freq[i]));
		}
	}
	return ans;
}
 
int main(){
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	while(q--){
		int idx, x; cin >> idx >> x;
		idx--;
		a[idx] = x;
		cout << calc(a) << "\n";
	}
}
 
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Full Credit:

The essential observation is: There exist at most $\sqrt{2N}$ distinct values in array $cnt$.

Consider the worst case, that is, $cnt = [1, 2, 3, \ldots, m, 0, 0, \ldots, 0]$. We know that $\sum_{i=1}^m cnt_i = N$, so $\frac{m \cdot (m+1)}{2} = N$. From this, we can deduce that $m$ must be at most $\sqrt{2N}$.

With this observation, we can realize that we only need to track the maximum and minimum elements of each distinct frequency that appears. Then, we can use the solution from the previous subtask. Given frequency $d$, to find the least frequency $k-d$ that appears, we can use two pointers.

The time complexity is $\mathcal{O}(N \log N + Q \sqrt{N})$.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int n, q; cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	vector<int> cnt(n+1);
	map<int, int> freq_mp; // freq_mp[i] stores the number of integers with occurrence i
	vector<set<int>> freqs(n+1); // freqs[i] stores a set of integers with occurrence i
	
	for(int i: a){
		cnt[i]++;
	}
	for(int i = 1; i <= n; i++){
		freq_mp[cnt[i]]++;
		freqs[cnt[i]].insert(i);
	}
	
	// change cnt[x] by c
	auto change = [&](int x, int c) -> void {
		freq_mp[cnt[x]]--;	
		if(!freq_mp[cnt[x]]) 
			freq_mp.erase(cnt[x]);
		freqs[cnt[x]].erase(x);
		cnt[x] += c;
		freq_mp[cnt[x]]++;
		freqs[cnt[x]].insert(x);
	};
	
	while(q--){
		int idx, x; cin >> idx >> x;
		idx--;
		change(a[idx], -1);
		a[idx] = x;
		change(a[idx], 1);
		
		vector<int> distinct_freqs;
		for(auto i: freq_mp){
			if(i.first){
				distinct_freqs.push_back(i.first);
			}
		}
		int m = distinct_freqs.size(); // m is at most approx sqrt(n)
		int mode_freq = distinct_freqs.back();
		
		vector<int> min_freq(m), max_freq(m); // max and min numbers with each frequency
		for(int i = 0; i < m; i++){
			min_freq[i] = *freqs[distinct_freqs[i]].begin();
			max_freq[i] = *freqs[distinct_freqs[i]].rbegin();
		}
		
		for(int i = m - 2; i >= 0; i--){
			max_freq[i] = max(max_freq[i], max_freq[i+1]);
		}
		
		int ans = 0;
		for(int l = 0, r = m - 1; l < m; l++){
			while(r - 1 >= 0 && distinct_freqs[r-1] + distinct_freqs[l] >= mode_freq){
				r--;
			}
			ans = max(ans, abs(max_freq[r] - min_freq[l]));
		}
		
		cout << ans << "\n";
	}
}
 
/*   /\_/\
*   (= ._.)
*   / >  \>
*/