stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



inline void read(int &x){

	x=0;int f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	x*=f;

}

/*******************************head*******************************/



const int N=200005;

int n,a[N],b[N];

inline bool check(int k){

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

	int l=n,r=n;

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

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

	if(l==1 && r==2*n-1){

		if(n&1) return b[n];

		else return (b[n]^1);

	}

	if(n-l<r-n)return b[l];

	else return b[r];

}

int main(){

	read(n);

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

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

	while(l<=r){

		int mid=(l+r)/2;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

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

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=200005;



int N,A[MAXN],B[MAXN];

bool check(int x)

{

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

	{

		if(A[N+i]>=x&&A[N+i+1]>=x)

			return true;

		if(A[N-i]>=x&&A[N-i-1]>=x)

			return true;

		if(A[N+i]<x&&A[N+i+1]<x)

			return false;

		if(A[N-i]<x&&A[N-i-1]<x)

			return false;

	}

	if(A[1]>=x)

		return true;

	return false;

}



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;

	while(L<R)

	{

		int mid=(L+R+1)/2;

		if(check(mid))

			L=mid;

		else

			R=mid-1;

	}

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

	return 0;

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

#include <iostream>

#include <cstring>

#include <cstdio>



using namespace std;



const int MAXN = 2e5 + 10;



int N;

int A[MAXN];

bool B[MAXN];



bool check(int mid)

{

	const int Nmid = (N + 1) >> 1;

	int Lft = 0, Rht = N + 1;



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

		B[i] = (A[i] >= mid);



	for (int i = Nmid; i > 1; i--)

		if (B[i] == B[i - 1])

		{

			Lft = i;

			break;

		}

	for (int i = Nmid; i < N; i++)

		if (B[i] == B[i + 1])

		{

			Rht = i;

			break;

		}

	if(Lft == 0 && Rht == N + 1)

		return B[1];

	else if(Nmid - Lft > Rht - Nmid)

		return B[Rht];

	else

		return B[Lft];

}



int main()

{

	cin >> N;

	N = (N << 1) - 1;

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

		cin >> A[i];



	// [L, R)

	int L = 1, R = N + 1;

	while (L + 1 < R)

	{

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

		//cerr << L << " " << mid << " " << R << endl ;



		if (check(mid))

			L = mid;

		else

			R = mid;

	}



	cout << L << endl;



	return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=200005;



int N,A[MAXN],B[MAXN];

bool check(int x)

{

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

	{

		if(A[N+i]>=x&&A[N+i+1]>=x)

			return true;

		if(A[N-i]>=x&&A[N-i-1]>=x)

			return true;

		if(A[N+i]<x&&A[N+i+1]<x)

			return false;

		if(A[N-i]<x&&A[N-i-1]<x)

			return false;

	}

	if(A[1]>=x)

		return true;

	return false;

}



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;

	while(L<R)

	{

		int mid=(L+R+1)/2;

		if(check(mid))

			L=mid;

		else

			R=mid-1;

	}

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

	return 0;

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

#include<cstdio>

 

const int MAXN=1e5+5;

 

int n;

int a[MAXN<<1];

bool jud(int k)

{

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

	{

		if(a[n+i]<k&&a[n+i+1]<k) return false;

		if(a[n-i]<k&&a[n-i-1]<k) return false;

		if(a[n+i]>=k&&a[n+i+1]>=k) return true;

		if(a[n-i]>=k&&a[n-i-1]>=k) return true;

	}

	return a[1]>=k;

}

 

int main()

{

	int i;scanf("%d",&n);

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

	int l=0,r=n<<1;

	while(l<=r)

	{

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

		if(jud(mid)) l=mid+1;

		else r=mid-1;

	}

	printf("%d",r);

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=200005;

long long n,N;

long long a[MAXN];

bool check(long long mid)

{

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

	{

		long long s0=0,s1=0;

		if(a[n-i]>=mid&&a[n-i-1]>=mid)

			s1++;

		if(a[n-i]<mid&&a[n-i-1]<mid)

			s0++;

		if(a[n+i]>=mid&&a[n+i+1]>=mid)

			s1++;

		if(a[n+i]<mid&&a[n+i+1]<mid)

			s0++;

		if(s1)

			return 1;

		if(s0)

			return 0;

	}

	return a[1]>=mid;

}

int main()

{

	//freopen("mid.in","r",stdin);

	//freopen("mid.out","w",stdout);

	scanf("%lld",&n);

	N=2*n-1;

	for(long long i=1;i<=N;i++)

	{

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

	}

	long long l=2,r=N,ans=1;

	while(l<=r)

	{

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

		if(check(mid))

		{

			ans=mid;

			l=mid+1;

		}

		else

			r=mid-1;

	}

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

	fclose(stdin);

	fclose(stdout);

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

using namespace std;

const int maxn = 200010;

int a[maxn],n,k;

bool b[maxn];

int main()

{

	scanf("%d",&n); 

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

	int L = 1, R = (int) 1e9;

	while (L <= R)

	{

	//	cerr<<L<<' '<<R<<endl;

		int mid = L + R >> 1; k = mid;

		for (int i = 1; i <= (n << 1) - 1; ++i) b[i] = (a[i] > k);

	//	for (int i = 1; i <= (n << 1) - 1; ++i) printf("%d",b[i]); putchar(10);

		int ok = -1;

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

		{

			if ((b[n + i] && b[n + i + 1])||(b[n - i] && b[n - i - 1])){ ok = 1; break;}

			if ((!b[n + i] && !b[n + i + 1]) || (!b[n - i] && !b[n - i - 1])) {ok = 0; break;}

		}

		if (ok == -1) ok = b[1];

		if (ok) L = mid + 1; else R = mid - 1;

	}

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

}

//二分答案k

//<=答案k的那些数都看成0。>k的那些数看成1. 当二分到的k >= 实际答案时,顶端为0，否则为1. 

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

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=200005;

long long n,N;

long long a[MAXN];

bool check(long long mid)

{

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

	{

		long long s0=0,s1=0;

		if(a[n-i]>=mid&&a[n-i-1]>=mid)

			s1++;

		if(a[n-i]<mid&&a[n-i-1]<mid)

			s0++;

		if(a[n+i]>=mid&&a[n+i+1]>=mid)

			s1++;

		if(a[n+i]<mid&&a[n+i+1]<mid)

			s0++;

		if(s1)

			return 1;

		if(s0)

			return 0;

	}

	return a[1]>=mid;

}

int main()

{

	//freopen("mid.in","r",stdin);

	//freopen("mid.out","w",stdout);

	scanf("%lld",&n);

	N=2*n-1;

	for(long long i=1;i<=N;i++)

	{

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

	}

	long long l=2,r=N,ans=1;

	while(l<=r)

	{

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

		if(check(mid))

		{

			ans=mid;

			l=mid+1;

		}

		else

			r=mid-1;

	}

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

	fclose(stdin);

	fclose(stdout);

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

using namespace std;



inline void read(int &x){

	x=0;int f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	x*=f;

}

/*******************************head*******************************/



const int N=200005;

int n,a[N],b[N];

inline bool check(int k){

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

	int l=n,r=n;

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

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

	if(l==1 && r==2*n-1){

		if(n&1) return b[n];

		else return (b[n]^1);

	}

	if(n-l<r-n)return b[l];

	else return b[r];

}

int main(){

	read(n);

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

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

	while(l<=r){

		int mid=(l+r)/2;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

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

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=200005;

long long n,N;

long long a[MAXN];

bool check(long long mid)

{

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

	{

		long long s0=0,s1=0;

		if(a[n-i]>=mid&&a[n-i-1]>=mid)

			s1++;

		if(a[n-i]<mid&&a[n-i-1]<mid)

			s0++;

		if(a[n+i]>=mid&&a[n+i+1]>=mid)

			s1++;

		if(a[n+i]<mid&&a[n+i+1]<mid)

			s0++;

		if(s1)

			return 1;

		if(s0)

			return 0;

	}

	return a[1]>=mid;

}

int main()

{

	//freopen("mid.in","r",stdin);

	//freopen("mid.out","w",stdout);

	scanf("%lld",&n);

	N=2*n-1;

	for(long long i=1;i<=N;i++)

	{

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

	}

	long long l=2,r=N,ans=1;

	while(l<=r)

	{

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

		if(check(mid))

		{

			ans=mid;

			l=mid+1;

		}

		else

			r=mid-1;

	}

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

	fclose(stdin);

	fclose(stdout);

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

#include <iostream>

#include <cstring>

#include <cstdio>



using namespace std;



const int MAXN = 2e5 + 10;



int N;

int A[MAXN];

bool B[MAXN];



bool check(int mid)

{

	const int Nmid = (N + 1) >> 1;

	int Lft = 0, Rht = N + 1;



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

		B[i] = (A[i] >= mid);



	for (int i = Nmid; i > 1; i--)

		if (B[i] == B[i - 1])

		{

			Lft = i;

			break;

		}

	for (int i = Nmid; i < N; i++)

		if (B[i] == B[i + 1])

		{

			Rht = i;

			break;

		}

	if(Lft == 0 && Rht == N + 1)

		return B[1];

	else if(Nmid - Lft > Rht - Nmid)

		return B[Rht];

	else

		return B[Lft];

}



int main()

{

	cin >> N;

	N = (N << 1) - 1;

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

		cin >> A[i];



	// [L, R)

	int L = 1, R = N + 1;

	while (L + 1 < R)

	{

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

		//cerr << L << " " << mid << " " << R << endl ;



		if (check(mid))

			L = mid;

		else

			R = mid;

	}



	cout << L << endl;



	return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=200005;

long long n,N;

long long a[MAXN];

bool check(long long mid)

{

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

	{

		long long s0=0,s1=0;

		if(a[n-i]>=mid&&a[n-i-1]>=mid)

			s1++;

		if(a[n-i]<mid&&a[n-i-1]<mid)

			s0++;

		if(a[n+i]>=mid&&a[n+i+1]>=mid)

			s1++;

		if(a[n+i]<mid&&a[n+i+1]<mid)

			s0++;

		if(s1)

			return 1;

		if(s0)

			return 0;

	}

	return a[1]>=mid;

}

int main()

{

	//freopen("mid.in","r",stdin);

	//freopen("mid.out","w",stdout);

	scanf("%lld",&n);

	N=2*n-1;

	for(long long i=1;i<=N;i++)

	{

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

	}

	long long l=2,r=N,ans=1;

	while(l<=r)

	{

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

		if(check(mid))

		{

			ans=mid;

			l=mid+1;

		}

		else

			r=mid-1;

	}

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

	fclose(stdin);

	fclose(stdout);

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

using namespace std;

const int maxn = 1e6 + 7;

int n, a[maxn];

int S(int i, int j, int k) {return a[i] <= k && a[j] <= k;}

int M(int i, int j, int k) {return a[i] > k && a[j] > k;}

int check(int k) {

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

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

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

	}

	return S(1, 1, k);

} 

int main() {

	scanf("%d", &n);

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

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

	while(l <= r) {

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

		if(check(mid)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.242092260858227x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

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

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200010

using namespace std;

int n,l,r,mid;

int a[MAXN];

inline bool check_large(int x,int y)

{

    if(a[x]>mid&&a[y]>mid) return true;

    return false;

}

inline bool check_small(int x,int y)

{

    if(a[x]<=mid&&a[y]<=mid) return true;

    return false;

}

inline bool solve()

{

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

    {

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

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

    }

    if(a[1]<=mid) return false;

    else return true;

}

int main()

{

    scanf("%d",&n);

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

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

    while(l<r)

    {

        mid=(l+r)>>1;

        if(solve()==true) l=mid+1;

        else r=mid; 

    }

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

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.240854436348843x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

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

using namespace std;

int n,a[20000010];

bool s(int i,int j,int k)

{

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

}

bool b(int i,int j,int k)

{

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

}

bool check(int k)

{

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

	{

        if(b(n+i,n+i+1,k)||b(n-i,n-i-1,k))

			return 0;

        if(s(n+i,n+i+1,k)||s(n-i,n-i-1,k))

			return 1;

    }

    return s(1,1,k);

}

int main()

{

    scanf("%d",&n);

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

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

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

    while(l<r)

	{

        int mid=l+(r-l)/2;

        if(check(mid))

            r=mid;

        else

			l=mid+1;

    }

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

    return 0; 

}

// Faster C++ solution for the same problem (measured speedup: 5.241447685091286x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

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

#include<cstdio>

using namespace std;

int n,a[200010];

bool check(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(){

    cin>>n;

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

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

    int ans=0;

    while(l<r){

        int mid=(l+r)/2;

        if(check(mid)){

            r=mid;ans=mid;

        }

        else l=mid+1;

    }

    cout<<ans<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 5.322955299538494x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

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

using namespace std;

int n;

vector<int>v,v2;

bool check(int x){

    v2.clear();

    for(int i=0;i<2*n-1;i++)v2.push_back(v[i]>=x);

    if(v[n-1]>=x&&v[n-2]>=x)return 1;

    if(v[n-1]>=x&&v[n]>=x)return 1;

    if(v[n-1]<x&&v[n-2]<x)return 0;

    if(v[n-1]<x&&v[n]<x)return 0;

    int l=n-2,r=n;

    while(l>0&&v2[l]!=v2[l-1])l--;

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

    if(r-l==2*n-2)return v2[l]; 

    if((r-l+1)%2)return v2[l];//ÏàÍ¬ 

    if(n-1-l<r-n+1)return v2[l];//ÀëµÃ¸ü¶Ì 

    return v2[r];

}

int main(){

    cin>>n;

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

        int a;

        cin>>a;

        v.push_back(a);

    }

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

    while(l<r){

        int mid=(l+r+1)/2;

        if(check(mid))

            l=mid;

        else

            r=mid-1;

        //cout<<l<<' '<<r<<endl;

    }

    cout<<l;

}

// Faster C++ solution for the same problem (measured speedup: 5.319453649210655x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

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

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstring>



#define reg register

#define MAX_N 200007

#define rep(i, l, r) for(int i = l; i <= r; ++i)

typedef long long ll;



template <typename _T>

inline bool read (_T& x) {

    x = 0;

    _T y = 1;

    char c = getchar();

    while ((c < '0' || '9' < c) && c != EOF) {

        if (c == '-') y = -1;

        c = getchar();

    }

    if (c == EOF) return false;

    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();

    x *= y;

    return true;

}



int M, N;

int a[MAX_N], b[MAX_N], c[MAX_N];



inline int calc (int x) {

    rep (i, 1, N) b[i] = (x < a[i]);

    // printf("%d:\n", x);

    // rep (i, 1, N) printf("%d ", b[i]); puts("");

    for (int i = 1, j = 1; i <= N; i = j) {

        int l, r;

        while (j < N && b[j + 1] == b[j]) j++;

        l = j;

        while (j < N && b[j + 1] != b[j]) j++;

        r = j;

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

        if (b[l] == b[r]) {

            rep (k, l + 1, r - 1) b[k] = b[l];

        } else {

            int sum = 0;

            rep (k, l, r) sum += (b[k] == b[l]);

            rep (k, l, l + sum - 1) b[k] = b[l];

            rep (k, l + sum, r) b[k] = b[r];

        }

        j++;

    }

    // rep (i, 1, N) printf("%d ", b[i]); puts("");

    return b[M];

}



int main () {

    //freopen ("triangle.in", "r", stdin);

    //freopen ("triangle.out", "w", stdout);

    read(M), N = 2 * M - 1;

    rep (i, 1, N) read(a[i]), c[i] = a[i];

    std::sort(c + 1, c + N + 1);

    int l = 1, r = N, mid, ans = 0;

    while (l <= r) {

        mid = l + r >> 1;

        if (!calc(c[mid])) ans = mid, r = mid - 1;

        else l = mid + 1;

    }

    printf("%d\n", c[ans]);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.2328409054248874x):
/*******************************

Author:Morning_Glory

LANG:C++

Created Time:2019年07月23日 星期二 10时12分43秒

*******************************/

#include <cstdio>

#include <fstream>

#include <algorithm>

using namespace std;

const int maxn = 200005;

//{{{cin

struct IO{

	template<typename T>

	IO & operator>>(T&res){

		res=0;

		bool flag=false;

		char ch;

		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';

		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();

		if (flag)	 res=~res+1;

		return *this;

	}

}cin;

//}}}

int n,m,l,r;

int a[maxn],b[maxn],c[maxn];

bool flag=true;

bool check (int x)

{

	int tl=m,tr=m,ans=c[m];

	c[0]=c[1],c[n+1]=c[n];

	for (;tl>=1&&c[tl]!=c[tl-1]&&c[tr]!=c[tr+1];--tl,++tr)	ans^=1;

	return ans;

}

int main()

{

	cin>>m;

	n=2*m-1;

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

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

	l=1,r=n;

	while (l<r){

		int mid=(l+r)/2+1;

		for (int i=1;i<=n;++i)	c[i]=a[i]>=b[mid];

		if (check(mid))	l=mid;

		else	r=mid-1;

	}

	printf("%d\n",b[l]);

	return 0;

}