Three Groups MEX

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MOD (int) 1e9 + 7
#define all(x) begin(x), end(x)
typedef long long ll;
using namespace std;
template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v) {
    for (auto &it : v)
        cin >> it;
    return istream;
}
template <typename T> // cout << vector<T>
ostream &operator<<(ostream &ostream, const vector<T> &c) {
    for (auto &it : c)
        cout << it << " ";
    return ostream;
}

bool ok(vector<int>& a, int x) {
    int mn = INT_MAX, mx = INT_MIN;
    int partitions = 0;
    for(int i = 0; i < a.size(); i++) {
        mn = min(a[i], mn);
        mx = max(a[i], mx);
        if(mx - mn > x) {
            partitions++;
            mn = a[i];
            mx = a[i];
        }
    }
    return partitions <= 2;
}

void solve(void) 
{
    int n; cin >> n;
    vector<int> a(n); cin >> a;
    sort(all(a));
    int l = 0, r = *max_element(all(a)) - *min_element(all(a));
    while(r - l > 1) {
        int m = (l + r) >> 1;
        if(ok(a, m)) {
            r = m;
        }
        else l = m + 1;
    }

    if(ok(a, l)) {
        cout << l;
    }
    else cout << r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}