cat O(nlogmaxs)

#include<stdio.h>
typedef long long int ll;

int main()
{
    int n;
    scanf("%d",&n);
    ll maxs = 0;
    ll cats[n];
    for(int i = 0 ; i < n ; i ++){
        scanf("%lld",&cats[i]);
        if(cats[i] > maxs)maxs = cats[i];
    }

    ll L = 0 , R = maxs;
    ll ans = 0;
    while(L <= R){
        ll M = (L+R)/2;
        ll prev = -1;
        bool check = true;
        for(int i = 0 ; i < n && check ; i ++){
            if(cats[i] <= M){
                continue;
            }else{
                if(prev == -1){
                    prev = cats[i];
                }else{
                    if(cats[i] != prev){
                        check = false;
                    }
                    prev = -1;
                }
            }
        }
        if(check){
            ans = M;
            R = M - 1;
        }else{
            L = M + 1;
        }
    }
    printf("%lld",ans);
    return 0;
}