## Editorial for Bedao Mini Contest 03 - COVIGAME

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int maxn = (int)1e5 + 7;

int a[maxn], low[maxn], high[maxn], F[maxn], G[maxn];
vector <int> V[maxn];

int main()
{
freopen("COVIGAME.INP", "r", stdin);
freopen("COVIGAME.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k, mi = INT_MAX;
cin >> n >> k;

for (int i = 1; i <= n; ++i)
{
cin >> a[i];
V[a[i]].push_back(i);
if (i > 1) F[i] = F[i - 1] + (abs(a[i] - a[i - 1]) > k);
}

for (int i = 2; i <= n; ++i)
if (a[i] == a[i - 1]) low[i] = low[i - 1];
else low[i] = i - 1;

for (int i = n - 1; i > 0; --i)
if (a[i] == a[i + 1]) high[i] = high[i + 1];
else high[i] = i + 1;

F[n + 1] = F[n] + 1;
for (int f = 1; f <= n; ++f)
{
int i = a[f];
if (G[i]) continue;
for (int j = 1; j < (int)V[i].size(); ++j)
G[i] += max(0, F[V[i][j] - 1] - F[V[i][j - 1] + 1]);
if (V[i].size()) G[i] += F[V[i][0] - 1] + max(0, F[n] - F[V[i].back() + 1]);
}

for (int i = 1; i <= n; ++i)
G[a[i]] += (low[i] && high[i] && abs(a[low[i]] - a[high[i]]) > k && a[i] != a[i - 1]);

for (int i = 1; i <= n; ++i) mi = min(mi, G[a[i]]);
int p = maxn;
for (int i = 1; i <= n; ++i)
if (G[a[i]] == mi) p = min(p, a[i]);
cout << p;
return 0;
}