stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 400020

using namespace std;

int read(){

	int nm=0,fh=1;char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

int n,m,L,R,md,t[M],ans,p[M],t1,t2;

bool solve(int x){

	t1=0,t2=(n<<1);

	for(int i=1;i<=m;i++) p[i]=(t[i]>=x);

	for(int i=2;i<=n;i++) if(p[i]==p[i-1]) t1=i;

	for(int i=m-1;i>=n;i--) if(p[i]==p[i+1]) t2=i;

	if(t1==n||t2==n) return p[n]>0;

	if(t1>1&&t2<m&&p[t1]==p[t2]) return p[t1]>0;

	if(t2-n<n-t1) return p[t2]>0;

	if(t2-n>n-t1) return p[t1]>0;

	return (p[n]^(n&1)^1)>0;

}

int main(){

	n=read(),L=1,R=n,R<<=1,R--,m=R;

	for(int i=1;i<=n+n-1;i++) t[i]=read();

    while(L<=R){

    	md=(L+R>>1);

    	if(!solve(md)) R=md-1;

		else L=md+1,ans=md;

	}

	printf("%d\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.154769199718883x):
//AT2165

#include <cstdio>



const int MAXN = (int)1e5;

int n, a[2*MAXN+5];



inline bool check(int x) {

	for (int i = 0; i < n-1; i++) {

		if ((a[n+i] <= x && a[n+i+1] <= x) || (a[n-i] <= x && a[n-i-1] <= x)) return true;

		if ((a[n+i] > x && a[n+i+1] > x) || (a[n-i] > x && a[n-i-1] > x)) return false;

	}

	return a[1] <= x;

}



int main() {

	scanf("%d", &n);

	for (register int i = 1; i < 2*n; i++)

		scanf("%d", a+i);

	int L = 0, R = 2*n-1;

	while (L < R) {

		int mid = (L+R)>>1;

		if (check(mid)) R = mid;

		else L = mid + 1;

	}

	printf("%d", L);

	return 0;

}
// Slower C++ solution:
/*

---------------------------------

题解：

我还是太蒟了，没有想到能二分答案……

我们二分塔顶的值，把小于等于这个值的变为1，大于变为0。

我们可以发现如果有多个个1或0连在一起，那么他们就无法被分开，他会一直往上走。

那也就是说，最后那组先走到顶那组就赢了，那就要看那组离中心更近。

那会不会存在两个不同阵营的组距离一样远能，你会发现这是不可能的。

因为，如果距离相等，那么中间一定是奇数个位置，我们用1和0,交替隔开两组，

那么最后一个位置肯定会和左边或者右边一样，又形成一个组，所这两个组要么都是1，要么都是0。

解决了这些问题就能愉快的判断了！

CODE：

---------------------------------题解1



最后还有一种特殊情况。就是没有任何两个相邻的。

大概长这样。。

    0

  0 1 0

0 1 0 1 0

我们只需要特判一下就行了。

总结，一道二分贪心题，需要一定的手推过程找到规律。

---------------------------------题解2

*/

#include<iostream>

#include<cstdio>

#include<cassert>

using namespace std;



int n,a[200005];



inline bool check(const int &k){

    if((a[n-1]<=k&&a[n]<=k)||(a[n]<=k&&a[n+1]<=k))return 1;

    if((a[n-1]> k&&a[n]> k)||(a[n]> k&&a[n+1]> k))return 0;

    for(int i=1;i<n-1;i++){

        if((a[n+i]<=k&&a[n+i+1]<=k)||(a[n-i]<=k&&a[n-i-1]<=k))return 1;

        if((a[n+i]> k&&a[n+i+1]> k)||(a[n-i]> k&&a[n-i-1]> k))return 0;

    }

    return a[1]<=k;

}



int main(){

    scanf("%d",&n);

    for(int i=1;i<n<<1;i++)scanf("%d",a+i);

    int l=1,r=(n<<1)-1;

    while(l<r){//满足 l<=k<=r

        int mid=l+r>>1;

        if(check(mid))r=mid;//结果可能小于等于k

        else l=mid+1;//不可能-->结果大于k-->往右半部分搜

    }

    assert(l==r);

    printf("%d",l);

}

// Faster C++ solution for the same problem (measured speedup: 5.164471615553387x):
//AT2165

#include <cstdio>



const int MAXN = (int)1e5;

int n, a[2*MAXN+5];



inline bool check(int x) {

	for (int i = 0; i < n-1; i++) {

		if ((a[n+i] <= x && a[n+i+1] <= x) || (a[n-i] <= x && a[n-i-1] <= x)) return true;

		if ((a[n+i] > x && a[n+i+1] > x) || (a[n-i] > x && a[n-i-1] > x)) return false;

	}

	return a[1] <= x;

}



int main() {

	scanf("%d", &n);

	for (register int i = 1; i < 2*n; i++)

		scanf("%d", a+i);

	int L = 0, R = 2*n-1;

	while (L < R) {

		int mid = (L+R)>>1;

		if (check(mid)) R = mid;

		else L = mid + 1;

	}

	printf("%d", L);

	return 0;

}
// Slower C++ solution:
#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

int n,m,a[500050],k,b[500050],ans,ok[2];

int check(int x)

{

	ok[0]=ok[1]=1000000;

	for(int i=1;i<=k;i++)

	b[i]=(a[i]>=x);

	b[0]=b[k+1]=10;

	for(int i=1;i<=k;i++)

	{

		if(b[i]==b[i-1]||b[i]==b[i+1])

		{

			ok[b[i]]=min(ok[b[i]],abs(i-n));

		}

	}

	//cout<<x<<" "<<ok[0]<<" "<<ok[1]<<endl;

	if(ok[1]==ok[0]) return b[1];

	return ok[1]<ok[0];

}

int main()

{

	cin>>n;

	k=2*n-1;

	for(int i=1;i<=k;i++)

	{

		scanf("%d",&a[i]);

	}

	int l=1,r=k;

	while(l<=r)

	{

		int mid=(l+r)/2;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	cout<<ans;

}

// Faster C++ solution for the same problem (measured speedup: 5.241840090495634x):
//AT2165

#include <cstdio>



const int MAXN = (int)1e5;

int n, a[2*MAXN+5];



inline bool check(int x) {

	for (int i = 0; i < n-1; i++) {

		if ((a[n+i] <= x && a[n+i+1] <= x) || (a[n-i] <= x && a[n-i-1] <= x)) return true;

		if ((a[n+i] > x && a[n+i+1] > x) || (a[n-i] > x && a[n-i-1] > x)) return false;

	}

	return a[1] <= x;

}



int main() {

	scanf("%d", &n);

	for (register int i = 1; i < 2*n; i++)

		scanf("%d", a+i);

	int L = 0, R = 2*n-1;

	while (L < R) {

		int mid = (L+R)>>1;

		if (check(mid)) R = mid;

		else L = mid + 1;

	}

	printf("%d", L);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int n,a[20000010];

bool x(int i,int j,int k) {

    return a[i]<=k&&a[j]<=k;

}

bool y(int i,int j,int k){

    return a[i]>k&&a[j]>k;

} 

bool check(int a){

    for(int i=0;i<n-1;i++){

        if(y(n+i,n+i+1,a)||y(n-i,n-i-1,a)) return 0;

        if(x(n+i,n+i+1,a)||x(n-i,n-i-1,a)) return 1;

    }

    return x(1,1,a);

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=2*n-1;i++) scanf("%d",&a[i]);

    int l=1,r=2*n-1,mid;

    while(l<r){

	 	mid=(l+r)/2;

        if(check(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d",l);

    return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 5.162412587778971x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 400020

using namespace std;

int read(){

	int nm=0,fh=1;char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

int n,m,L,R,md,t[M],ans,p[M],t1,t2;

bool solve(int x){

	t1=0,t2=(n<<1);

	for(int i=1;i<=m;i++) p[i]=(t[i]>=x);

	for(int i=2;i<=n;i++) if(p[i]==p[i-1]) t1=i;

	for(int i=m-1;i>=n;i--) if(p[i]==p[i+1]) t2=i;

	if(t1==n||t2==n) return p[n]>0;

	if(t1>1&&t2<m&&p[t1]==p[t2]) return p[t1]>0;

	if(t2-n<n-t1) return p[t2]>0;

	if(t2-n>n-t1) return p[t1]>0;

	return (p[n]^(n&1)^1)>0;

}

int main(){

	n=read(),L=1,R=n,R<<=1,R--,m=R;

	for(int i=1;i<=n+n-1;i++) t[i]=read();

    while(L<=R){

    	md=(L+R>>1);

    	if(!solve(md)) R=md-1;

		else L=md+1,ans=md;

	}

	printf("%d\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.15202099986065x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
/*

---------------------------------

题解：

我还是太蒟了，没有想到能二分答案……

我们二分塔顶的值，把小于等于这个值的变为1，大于变为0。

我们可以发现如果有多个个1或0连在一起，那么他们就无法被分开，他会一直往上走。

那也就是说，最后那组先走到顶那组就赢了，那就要看那组离中心更近。

那会不会存在两个不同阵营的组距离一样远能，你会发现这是不可能的。

因为，如果距离相等，那么中间一定是奇数个位置，我们用1和0,交替隔开两组，

那么最后一个位置肯定会和左边或者右边一样，又形成一个组，所这两个组要么都是1，要么都是0。

解决了这些问题就能愉快的判断了！

CODE：

---------------------------------题解1



最后还有一种特殊情况。就是没有任何两个相邻的。

大概长这样。。

    0

  0 1 0

0 1 0 1 0

我们只需要特判一下就行了。

总结，一道二分贪心题，需要一定的手推过程找到规律。

---------------------------------题解2

*/

#include<iostream>

#include<cstdio>

#include<cassert>

using namespace std;



int n,a[200005];



inline bool check(const int &k){

    if((a[n-1]<=k&&a[n]<=k)||(a[n]<=k&&a[n+1]<=k))return 1;

    if((a[n-1]> k&&a[n]> k)||(a[n]> k&&a[n+1]> k))return 0;

    for(int i=1;i<n-1;i++){

        if((a[n+i]<=k&&a[n+i+1]<=k)||(a[n-i]<=k&&a[n-i-1]<=k))return 1;

        if((a[n+i]> k&&a[n+i+1]> k)||(a[n-i]> k&&a[n-i-1]> k))return 0;

    }

    return a[1]<=k;

}



int main(){

    scanf("%d",&n);

    for(int i=1;i<n<<1;i++)scanf("%d",a+i);

    int l=1,r=(n<<1)-1;

    while(l<r){//满足 l<=k<=r

        int mid=l+r>>1;

        if(check(mid))r=mid;//结果可能小于等于k

        else l=mid+1;//不可能-->结果大于k-->往右半部分搜

    }

    assert(l==r);

    printf("%d",l);

}

// Faster C++ solution for the same problem (measured speedup: 5.1617182429751365x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

int n,m,a[500050],k,b[500050],ans,ok[2];

int check(int x)

{

	ok[0]=ok[1]=1000000;

	for(int i=1;i<=k;i++)

	b[i]=(a[i]>=x);

	b[0]=b[k+1]=10;

	for(int i=1;i<=k;i++)

	{

		if(b[i]==b[i-1]||b[i]==b[i+1])

		{

			ok[b[i]]=min(ok[b[i]],abs(i-n));

		}

	}

	//cout<<x<<" "<<ok[0]<<" "<<ok[1]<<endl;

	if(ok[1]==ok[0]) return b[1];

	return ok[1]<ok[0];

}

int main()

{

	cin>>n;

	k=2*n-1;

	for(int i=1;i<=k;i++)

	{

		scanf("%d",&a[i]);

	}

	int l=1,r=k;

	while(l<=r)

	{

		int mid=(l+r)/2;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	cout<<ans;

}

// Faster C++ solution for the same problem (measured speedup: 5.2390454698956725x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int RLEN=1<<18|1;

inline char nc() {

    static char ibuf[RLEN],*ib,*ob;

    (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));

    return (ib==ob) ? -1 : *ib++;

}

inline int rd() {

    char ch=nc(); int i=0,f=1;

    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}

    while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}

    return i*f;

}



const int N=2e5+50;

int n,a[N];

#define up(i,j) ((a[i]>=v) && (a[j]>=v))

#define dn(i,j) ((a[i]<v) && (a[j]<v))

inline bool check(int v) {

    for(int i=0;i<n-1;i++) {

        if(up(n+i,n+i+1) || up(n-i,n-i-1)) return 1;

        if(dn(n+i,n+i+1) || dn(n-i,n-i-1)) return 0;

    } return up(1,1);

}

int main() {

    n=rd(); for(int i=1;i<n*2;++i) a[i]=rd();

    int l=1, r=*max_element(a+1,a+2*n), ans=0;

    while(l<=r) {

        int mid=(l+r)>>1;

        if(check(mid)) ans=mid, l=mid+1;

        else r=mid-1;

    } cout<<ans<<'\n';

}

// Faster C++ solution for the same problem (measured speedup: 5.206452853667559x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 200005

using namespace std;

int a[N],len,n;

bool f[N];

bool check(int x){

	for(int i=1;i<=len;++i) f[i]=a[i]>=x;

	for(int i=0;i<n-1;++i){

		if((f[n+i]&&f[n+i+1])||(f[n-i]&&f[n-i-1])) return 1;

		else if((!f[n+i]&&!f[n+i+1])||(!f[n-i]&&!f[n-i-1])) return 0;

	}

	return f[1];

}

int main(){

	int l=1,r,i,ans;

	scanf("%d",&n);r=len=2*n-1;

	for(i=1;i<=len;++i) scanf("%d",&a[i]);

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	cout<<ans;

}

// Faster C++ solution for the same problem (measured speedup: 5.180572301163495x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int n,a[200001];

bool checx(int x)

{

    if((a[n-1]<=x&&a[n]<=x)||(a[n]<=x&&a[n+1]<=x))return 1;

    if((a[n-1]> x&&a[n]> x)||(a[n]> x&&a[n+1]> x))return 0;

    for(int i=1;i<n-1;i++){

        if((a[n+i]<=x&&a[n+i+1]<=x)||(a[n-i]<=x&&a[n-i-1]<=x))return 1;

        if((a[n+i]> x&&a[n+i+1]> x)||(a[n-i]> x&&a[n-i-1]> x))return 0;

    }

    return a[1]<=x;

}



int main(){

    cin>>n;

    for(int i=1;i<n<<1;i++)cin>>a[i];

    int l=1,r=(n<<1)-1;

    while(l<r)

	{

        int mid=(l+r)/2;

        if(checx(mid))r=mid;

        else l=mid+1;

    }

    cout<<l;

}


// Faster C++ solution for the same problem (measured speedup: 5.223824151345118x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <algorithm>



using namespace std;



const int N = 100010;



int n, a[N << 1];



bool check(int x)

{

	int l = n, r = n;

	while (l > 1 && (a[l - 1] >= x) != (a[l] >= x)) --l;

	while (r < 2 * n - 1 && (a[r + 1] >= x) != (a[r] >= x)) ++r;

	if (n - l <= r - n) return a[l] >= x;

	return a[r] >= x;

}



int main()

{

	int l = 0x7fffffff, r = 0;

	

	scanf("%d", &n);

	

	for (int i = 1; i <= 2 * n - 1; ++i)

	{

		scanf("%d", a + i);

		l = min(l, a[i]);

		r = max(r, a[i]);

	}

	

	while (l < r)

	{

		int mid = (0ll + l + r + 1) >> 1;

		if (check(mid)) l = mid;

		else r = mid - 1;

	}

	

	cout << l;

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.1778905129804125x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define reg register

#define ll long long

inline ll read()

{

	ll x=0,w=0;char ch=getchar();

	while(!isdigit(ch))w|=ch=='-',ch=getchar();

	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

	return w?-x:x;

}

int n,m,a[200000],b[200000];

int main()

{

    m=read();n=m*2-1;reg int i,j,l,r,mid,c,fl;

    for(i=1;i<=n;++i)a[i]=read(),b[i]=a[i];

    sort(b+1,b+1+n);

    l=0;r=n;

    while(l<r-1)

    {

        mid=(l+r)>>1;c=(a[m]>b[mid]);c^=1;fl=-1;

        for(i=m-1,j=m+1;i>=1,j<=n;--i,++j)

        {

            if((a[i]>b[mid])!=c){fl=(a[i]>b[mid]);break;}

            if((a[j]>b[mid])!=c){fl=(a[j]>b[mid]);break;}

            c^=1;

        }

        if(fl==-1)

        {

            if(m&1)fl=(a[m]>b[mid]);

            else fl=(a[m]<=b[mid]);

        }

        if(fl)l=mid;

        else r=mid;

    }

    cout<<b[r]<<"\n";

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.215169746325279x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a[222222];

int n,l,r,ans,mid;

inline int big(int x,int y,int z){ return a[x]>z&&a[y]>z; }

inline int small(int x,int y,int z){ return a[x]<=z&&a[y]<=z; }

inline bool Trial(int k)

{

    for(register int i=0;i<n-1;++i)

    {

        if(big(n-i,n-i-1,k)||big(n+i,n+i+1,k)) return false;

        if(small(n-i,n-i-1,k)||small(n+i,n+i+1,k)) return true;

    }

    return small(1,1,k);

}

int main()

{

    scanf("%d",&n);

    for(register int i=1;i<(n<<1);++i) scanf("%d",&a[i]);

    l=1;r=n*2-1;

    while(l<r)

    {

        mid=(l+r)/2;

        if(Trial(mid)) r=mid;

        else l=mid+1;

    }

    ans=r;

    printf("%d\n",ans);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.165079514117144x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n,a[2000500],b[2000005],r,l;

void work(int x,int y){

	//cout<<x<<" "<<y<<endl;

	if((y-x)&1){

		if(n>=(y-x+1)/2){//cout<<"z"<<endl;

		    rep(i,x,(y+x)/2) b[i]=b[x];

		    rep(i,(y+x)/2+1,y) b[i]=b[y];

		}

		else{

			rep(i,x,x+n-1) b[i]=b[x];

			rep(i,x+n,y-n) if((i-x-n)%2==0) b[i]=b[x]; else b[i]=b[y];

			rep(i,y-n+1,y) b[i]=b[y];

		}

	}

	else{//cout<<"h";

	    rep(i,x,y) b[i]=b[x];

		if(n<=(y-x)/2) rep(i,x+n,y-n) if((i-x-n)%2==0) b[i]=1-b[x];else b[i]=b[x];

	}

}

bool check(int x){

//	cout<<x<<endl;

	rep(i,1,2*n-1) if(a[i]>=x) b[i]=1;else b[i]=0;

//	rep(i,1,2*n-1) cout<<b[i];cout<<endl;

	b[2*n]=2;

	int st=-1;

	rep(i,1,2*n-1){

		if(st!=-1 && b[i]==b[i+1]) work(st,i),st=-1;

		if(st==-1 && b[i]!=b[i+1]) st=i;

	}

	if(st!=-1) work(st,2*n-1);

//	rep(i,1,2*n-1) cout<<b[i];cout<<endl;

	return b[n];

}

int main(){

	scanf("%d",&n);

	rep(i,1,2*n-1) scanf("%d",&a[i]),r=max(r,a[i]);

    l=1;

    while(l<r){

    	int mid=(l+r+1)>>1;

    	if(check(mid)) l=mid;

    	else r=mid-1;

	}

	printf("%d",l);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.169224448717794x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int n;

int a[200005];

int ha1(int i,int j,int x)

{

	return a[i]>x&&a[j]>x;

}

int ha2(int i,int j,int x)

{

	return a[i]<=x&&a[j]<=x;

}

int haha(int x)

{

	for(int i=0;i<n;i++)

	{

		if(ha1(n+i,n+i+1,x)||ha1(n-i,n-i-1,x))//判断大的

			return 0;

		if(ha2(n+i,n+i+1,x)||ha2(n-i,n-i-1,x))

			return 1;

	}

	return ha2(1,1,x);

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n*2-1;i++)

		scanf("%d",&a[i]);

	int l=1,r=2*n-1;

	while(l<r)

	{

		int mid=(l+r)>>1;

		if(haha(mid))

			r=mid;

		else

			l=mid+1;

	}

	printf("%d\n",r);

}

// Faster C++ solution for the same problem (measured speedup: 5.203579396388309x):
#include<cstdio>

using namespace std;

const int MAXN=3e5+5;

int N;

int A[MAXN];



bool Check(int Key){

	for(int i=0;i<N-1;i++){

		if( (A[N+i]>Key && A[N+i+1]>Key) || (A[N-i]>Key && A[N-i-1]>Key) ){

			return 0;

		}

		if( (A[N+i]<=Key && A[N+i+1]<=Key) || (A[N-i]<=Key && A[N-i-1]<=Key) ){

			return 1;

		}

	}

	return A[1]<=Key;

}



int BS(int L,int R){

	int Ans=0;

	while(L<=R){

		int Mid=(L+R)>>1;

		if(Check(Mid)){

			Ans=Mid;

			R=Mid-1;

		}else{

			L=Mid+1;

		}

	}

	return Ans;

}



int main(){

	

	scanf("%d",&N);

	

	for(int i=1;i<=2*N-1;i++){

		scanf("%d",&A[i]);

	}

	

	printf("%d\n",BS(1,2*N-1));

	

	return 0;

	

}