cf982d Shark

ref
#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;

}
巴特西

cf982d Shark

最新文章

热门文章
