CF271C

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

int n;
ll a[300003];
ll v[300003];

int main(int argc, char **argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
        if (a[i] < 300003) {
            v[a[i]] = 1;
        }
    }
    for (int i = 0; i < 300003; ++i)
        v[i + 1] += v[i];
    int lb = 0, ub = 300003, cnt = ub - lb, step, it;
    while (cnt) {
        it = lb, step = cnt / 2, it += step;
        if (it < v[it] + (n - v[it]) / 2) {
            lb = it + 1;
            cnt -= step + 1;
        } else {
            cnt = step;
        }
    }
    if (v[lb + 1] + (n - v[lb + 1]) / 2 >= lb + 1)
        lb++;
    printf("%d\n", lb);
    return 0;
};