cf982d Shark

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> par;
int n;
par a[100005];
set<par> se;
map<int,int> mp;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a+1, a+1+n);
    se.insert(par(1, n));
    mp[n] = 1;
    int maxn=0, ans=-1;
    for(int i=n; i; i--){
        if(mp.size()==1 && mp.begin()->second>=maxn){
            maxn = mp.begin()->second;
            ans = a[i].first + 1;
        }
        set<par>::iterator it=se.upper_bound(par(a[i].second, 0x3f3f3f3f));
        it--;
        if(it->first<=a[i].second-1){
            par x(it->first, a[i].second-1);
            se.insert(x);
            mp[x.second-x.first+1]++;
        }
        if(a[i].second+1<=it->second){
            par x(a[i].second+1, it->second);
            se.insert(x);
            mp[x.second-x.first+1]++;
        }
        int len=it->second-it->first+1;
        se.erase(it);
        mp[len]--;
        if(!mp[len])    mp.erase(len);
    }
    cout<<ans<<endl;
    return 0;
}