TOI13: Cats

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 2e6;

lli cats[N + 1];
int nCats;

bool moveCats(lli m){
    bool isPairing = false;
    lli last = 0;
    for(int i = 1; i <= nCats; ++i){
        if(cats[i] > m){
            if(!isPairing){
                isPairing = true;
                last = cats[i];
            } else {
                if(cats[i] != last){
                    return false;
                }
                isPairing = false;
            }
        }
    }
    return true;
}

int main(){

    scanf("%d", &nCats);
    lli mx = 0;
    for(int i = 1; i <= nCats; ++i){
        scanf("%lld", &cats[i]);
        mx = max(mx, cats[i]);
    }
    lli l = 0;
    lli r = mx;
    lli ans = mx;
    while(l <= r){
        lli m = (l + r) / 2;
        if(moveCats(m)){
            ans = min(ans, m);
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    cout << ans;

    return 0;
}