TOI13: Cats

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

using lli = long long;
const lli INF = 2e18;
vector <lli> cat;

bool move(lli mid,int n){
    int bf = -1;
    set <lli> keep;
    for(int i=0;i<n;i++){
        if(cat[i] <= mid) continue;
        if(bf == cat[i]) {
            keep.erase(keep.find(bf));
            bf = -1;
        }
        else{
            bf = cat[i];
            if(keep.find(cat[i]) != keep.end()) return false;
            keep.insert(cat[i]);
        }
    }
    return true;
}

int main(){

    int n;
    lli l=0, r=-INF,mn=INF;
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        lli x;
        scanf("%lld",&x);
        cat.push_back(x);
        r = max(r,x);
    }

    while(l <= r){
        lli mid = (l+r)/2;
        if(move(mid,n)){
            r = mid-1;
            mn = min(mn, mid);

        }
        else
            l = mid+1;
    }
    printf("%lld",mn);

    return 0;
}