Submission #3011370

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define MAXN 100010
using namespace std;
ll n,a[MAXN],b[MAXN],ans;
inline bool check(ll x)
{
	for(int i=1;i<=2*n-1;i++){
		if(a[i]>=x) b[i]=1;
		else b[i]=0;
	}
	int l=n,r=n;
	while(l>1&&b[l-1]!=b[l]) l--;
	while(r<2*n-1&&b[r]!=b[r+1]) r++;
	if(l==1&&r==2*n+1){
		 return a[1]<=x && a[1]<=x;
	}
	else{
		if(n-l<r-n) return b[l];
		else return b[r];
	}
}
int main()
{
	ll l=1,r,mid;
	cin>>n;
	r=2*n-1;
	for(int i=1;i<=r;i++) cin>>a[i];
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans;
return 0;
}

Submission Info

Judge Result