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

#define rg register

#define LL long long 



using namespace std;



const int N=200010;

inline int read(){

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

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

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int n,a[N];

int l,r,ans;

bool check(int mid){

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

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

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

	}

	return a[1]<=mid;

}

int main()

{

	n=read();

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

		a[i]=read();

	l=1,r=(n<<1)-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.148244288727985x):
/************************************************

*Author        :  lrj124

*Created Time  :  2019.11.07.21:12

*Mail          :  1584634848@qq.com

*Problem       :  at2165

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

#include <cstdio>

const int maxn = 200000 + 10;

int n,l,r(maxn),x[maxn];

inline bool check(int mid) {

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

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

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

	}

	return x[1] <= mid;

}

int main() {

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

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

	scanf("%d",&n);

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

	for (int mid;l < r;mid = l+r>>1,check(mid) ? r = mid : l = mid+1);

	printf("%d",l);

	return 0;

}
// Slower C++ solution:
/*

ID:xmydada1

LANG:C++

TASK:

*/

#include<bits/stdc++.h>

#define reg register



using namespace std;

const int N=2e5+7;

int m,n,ans=0,sum=0,p,q;

int a[N],b[N];

inline int read() {

reg int s = 0, t = 0; reg char ch = getchar();

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

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

return t ? -s : s;

}



inline void print(reg long long x) {

if(x < 0) putchar('-'), x = -x;

if(x > 9) print(x / 10);

putchar(x % 10 + 48);

}

int main()

{

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

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

	n=read();n=n*2-1;

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

	int l=0,r=1e9+7;

	while(l<=r)

	{

		int mid=l+r>>1;

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

		{  

			if(a[i]>mid)b[i]=1;

			else b[i]=0;

		}

		b[n+1]=b[n];

		b[0]=b[1];

		p=0;

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

		{

			if(b[i-1]!=b[i]){p++;}

			if(b[i-1]==b[i]&&p)

			{

				if(p%2==0)for(int j=i-p;j<=i-1;j++)b[j]=b[i];

				else 

				{

					q=p>>1;

					for(int j=i-p;j<=i-q-2;j++)b[j]=b[i-p-1];

					for(int j=i-q-1;j<=i-1;j++)b[j]=b[i];	

				}

				p=0;

			}

		}

		

		if(b[n/2+1]){l=mid+1;}

		else {r=mid-1;ans=mid;}

		memset(b,0,sizeof(b));

	}

	printf("%d",ans);



return 0;

}




// Faster C++ solution for the same problem (measured speedup: 4.3400091307265685x):
#include<bits/stdc++.h>

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){

        int mid=l+r>>1;

        if(check(mid))r=mid;

        else l=mid+1;

    }

    printf("%d",l);

}
// Slower C++ solution:
/*

ID:xmydada1

LANG:C++

TASK:

*/

#include<bits/stdc++.h>

#define reg register



using namespace std;

const int N=2e5+7;

int m,n,ans=0,sum=0,p,q;

int a[N],b[N];

inline int read() {

reg int s = 0, t = 0; reg char ch = getchar();

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

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

return t ? -s : s;

}



inline void print(reg long long x) {

if(x < 0) putchar('-'), x = -x;

if(x > 9) print(x / 10);

putchar(x % 10 + 48);

}

int main()

{

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

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

	n=read();n=n*2-1;

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

	int l=0,r=1e9+7;

	while(l<=r)

	{

		int mid=l+r>>1;

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

		{  

			if(a[i]>mid)b[i]=1;

			else b[i]=0;

		}

		b[n+1]=b[n];

		b[0]=b[1];

		p=0;

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

		{

			if(b[i-1]!=b[i]){p++;}

			if(b[i-1]==b[i]&&p)

			{

				if(p%2==0)for(int j=i-p;j<=i-1;j++)b[j]=b[i];

				else 

				{

					q=p>>1;

					for(int j=i-p;j<=i-q-2;j++)b[j]=b[i-p-1];

					for(int j=i-q-1;j<=i-1;j++)b[j]=b[i];	

				}

				p=0;

			}

		}

		

		if(b[n/2+1]){l=mid+1;}

		else {r=mid-1;ans=mid;}

		memset(b,0,sizeof(b));

	}

	printf("%d",ans);



return 0;

}




// Faster C++ solution for the same problem (measured speedup: 4.370152909761614x):
#include<bits/stdc++.h>

#define rap(i,first,last) for(int i=first;i<=last;++i)

using namespace std;

const int maxN=2333333;

const int INF=114514233;

int N;

int arr[maxN];

bool boo[maxN];

bool check(int middle)

{

	rap(i,1,N*2-1)

	boo[i]=(arr[i]>=middle);

	int len1=INF,len0=INF;

	rap(i,1,N*2-2)

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

	{

		if(boo[i])

		len1=min(len1,min(abs(N-i),abs(N-i-1)));

		else

		len0=min(len0,min(abs(N-i),abs(N-i-1)));

	}

	if(len1!=INF||len0!=INF)return len1<len0;

	return (N&1)==boo[N];

}

int main()

{

	scanf("%d",&N);

	rap(i,1,N*2-1)scanf("%d",&arr[i]);

	int l=-1,r=N*2,mid,answer=-1;

	while(l<=r)

	{

		mid=(l+r)/2;

		if(check(mid))

		{

			answer=mid;

			l=mid+1;

		}

		else

		{

			r=mid-1;

		}

	}

	printf("%d",answer);

	return 0;

}
// Slower C++ solution:
/*

ID:xmydada1

LANG:C++

TASK:

*/

#include<bits/stdc++.h>

#define reg register



using namespace std;

const int N=2e5+7;

int m,n,ans=0,sum=0,p,q;

int a[N],b[N];

inline int read() {

reg int s = 0, t = 0; reg char ch = getchar();

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

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

return t ? -s : s;

}



inline void print(reg long long x) {

if(x < 0) putchar('-'), x = -x;

if(x > 9) print(x / 10);

putchar(x % 10 + 48);

}

int main()

{

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

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

	n=read();n=n*2-1;

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

	int l=0,r=1e9+7;

	while(l<=r)

	{

		int mid=l+r>>1;

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

		{  

			if(a[i]>mid)b[i]=1;

			else b[i]=0;

		}

		b[n+1]=b[n];

		b[0]=b[1];

		p=0;

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

		{

			if(b[i-1]!=b[i]){p++;}

			if(b[i-1]==b[i]&&p)

			{

				if(p%2==0)for(int j=i-p;j<=i-1;j++)b[j]=b[i];

				else 

				{

					q=p>>1;

					for(int j=i-p;j<=i-q-2;j++)b[j]=b[i-p-1];

					for(int j=i-q-1;j<=i-1;j++)b[j]=b[i];	

				}

				p=0;

			}

		}

		

		if(b[n/2+1]){l=mid+1;}

		else {r=mid-1;ans=mid;}

		memset(b,0,sizeof(b));

	}

	printf("%d",ans);



return 0;

}




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

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 200010

inline int read(){

	int x=0,f=1;

	char c=getchar();

	while(c<'0'||c>'9'){

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

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		x=(x<<1)+(x<<3)+c-'0';

		c=getchar();

	}

	return x*f;

}

int n,a[N],b[N],ans,l,r;

inline bool check(int x){

	int l=n-1,r=n+1;

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

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

	}

	while(l>=1){

		if(a[l]==a[l+1]){

			return a[l];

		}

		if(a[r]==a[r-1]){

			return a[r];

		}

		--l,++r;

	}

	return a[1];

}

int main(){

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

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

	n=read();

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

		b[i]=read();

	}

	l=1,r=1e8;

	while(l<r){

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

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else{

			r=mid;

		}

	}	

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

	return 0;

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

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

#define ft first

#define sd second

#define pb(a) push_back(a)

#define mp(a,b) std::make_pair(a,b)

#define ITR(a,b) for(auto a:b)

#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)

#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)

const int MAXN=2000000+10;

int n,A[MAXN],p[MAXN];

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

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

	if(ch=='-')w=-1,ch=getchar();

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

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline bool chkmin(T &x,T y){return y<x?(x=y,true):false;}

template<typename T> inline bool chkmax(T &x,T y){return y>x?(x=y,true):false;}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline bool check(int las)

{

	REP(i,1,n+n-1)p[i]=(A[i]>=las);

	if(p[n]==p[n-1])return p[n];

	if(p[n]==p[n+1])return p[n];

	REP(i,1,n-1)

	{

		if(p[n-i]==p[n-i+1])return p[n-i+1];

		if(p[n+i]==p[n+i-1])return p[n+i-1];

	}

	return p[n]^((n-1)&1);

}

int main()

{

	read(n);

	REP(i,1,n+n-1)read(A[i]);

	if(n==1)

	{

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

		return 0;

	}

	int l=1,r=n+n-1,ans=r;

	while(l<=r)

	{

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

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

		else r=mid-1;

	}

	write(ans,'\n');

	return 0;

}


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

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

}
// Slower C++ solution:
/*#include<bits/stdc++.h>         //暴力:(

using namespace std;  

int getint()

{

	char c;

	int ans=0,k=1;

	while(c=getchar(),c>'9' || c<'0') if(c=='-') k=-1;

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

	return ans*k;

}

const int N=2e6+5;

int a[N][2];

int n;

int work(int x,int y,int z)

{

	int t;

	if(x>y) t=x,x=y,y=t;

	if(y>z) t=y,y=z,z=t;

	return x>y?x:y; 

}

int main()

{

	freopen("pyramid.in","r",stdin);

	freopen("pyramid.out","w",stdout);

	scanf("%d",&n);

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

	bool t=0,s;

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

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

		s=!t;

		for(int j=l+i;j<=r-i;j++)

			a[j][s]=work(a[j-1][t],a[j][t],a[j+1][t]);

		t=!t;

	}

	cout<<a[n][s]<<endl;

}*/

#include<bits/stdc++.h>

using namespace std;

int getint()

{

	char c;

	int ans=0,k=1;

	while(c=getchar(),c>'9' || c<'0') if(c=='-') k=-1;

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

	return ans*k;

}

const int N=2e6+5;

int n;

int a[N];

inline 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()

{

	scanf("%d",&n);

	int left=0,right=(n<<1)-1;

	for(int i=1;i<=right;i++) a[i]=getint();

	int mid;

	while(left<=right){

		mid=left+right>>1;

		if(check(mid)) right=mid-1;

		else left=mid+1;

	}

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

	

}

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

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

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

#define MAXN 211111

using namespace std;

int num[MAXN], N, tmp[MAXN];

int main(){

    cin>>N;

    int i, l = 1, r = 2 * N;

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

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

    }

    int ans = 0;

    while(l <= r){

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

//		printf("mid=%d\n", mid); 

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

            tmp[i] = (num[i] >= mid?1 : 0);

   //         printf("%d ", tmp[i]);

        }                                  

//        puts("");

        bool flag = false, ok = false;

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

            if(tmp[N-i] == tmp[N-i+1]){

                if(tmp[N-i] == 1){

                    flag = ok = true;

                    break;

                }

                else {

                    ok = true;

                    break;

                }

            }

            if(tmp[N+i] == tmp[N+i-1]){

                if(tmp[N+i] == 1){

                    ok = flag = true;

                    break;

                }

                else {

                    ok = true;

                    break;

                }

            }

        }

//        printf("ok=%d flag=%d\n", ok, flag);

        if(ok == false){

        	if((tmp[N] == 0 && !(N & 1)) || (tmp[N] == 1 && N & 1 == 1))flag = true;	

        }

//    	printf("flag'=%d\n", flag);

        if(flag){

            ans = max(ans, mid);

            l = mid + 1;

        }

        else r = mid - 1;

    }

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

    return 0;

}

/*

写题目习惯不太好

不把该注意的条件写下来

4

4 1 5 2 6 3 7

*/ 

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

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

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



using namespace std;



#define N 100000



int n;

int a[2*N+5];



int 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 1;

		else 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() {

	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;

		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.181740442323478x):
#include<cstdio>

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

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



const int N = 200001;

using namespace std; 



int n,a[N]; 

bool b[N]; 



bool check(int x){ 

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

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

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

		if(b[n-i]==b[n-i-1])

			return b[n-i];

		if(b[n+i]==b[n+i+1])

			return b[n+i];} 

	return b[1]; 

} 



int main(){ 

	scanf("%d",&n);

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

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

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

	while(l<r)

		if(check(m=l+r>>1))

			r=m;

		else l=m+1; 

	printf("%d",l); 

}


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

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

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

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

void read(int &x){

	char ch;bool ok;

	for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;

	for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;

}

#define rg register

const int maxn=2e5+10;

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

bool check(int x){

	int sum=0;

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

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

		if(b[i])sum++;

		else sum--;

	}

	bool flag=0;

	for(rg int i=1;i<n;i++)if(b[i]==b[i+1])flag=1;

	if(!flag)return sum>0;

	int now=(n+1)>>1,now1=now;

	while(now1>1){

		if(b[now]==b[now+1])return b[now];

		if(b[now1]==b[now1-1])return b[now1];

		now++,now1--;

	}

}

int main(){

	read(n);n=(n<<1)-1;

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

	int l=1,r=n;

	while(l<=r){

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

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

		else r=mid-1;

	}

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

}


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

#include<algorithm>

using std::sort;

const int N=300011;

int a[N];

int n,m;

struct kkll

{

    int v,id;

    bool operator < (const kkll a)const{return v<a.v;}

}kll[N];

int pll[N],mar;

int b[N];



bool ck(int x)

{

    for(int i=1;i<=m;i++) if(a[i]<=x) b[i]=0;else b[i]=1;

    int p1=n,p2=n;

    while(p1>1)

    {

        if((b[p1]&b[p1-1])||(b[p2]&b[p2+1])) return 0;

        if(!(b[p1]|b[p1-1])||!(b[p2]|b[p2+1])) return 1;

        p1--,p2++;

    }

    return b[1]^1;

}





int main()

{

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

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

    scanf("%d",&n);

    m=n*2-1;

    for(int i=1;i<=m;i++) scanf("%d",&a[i]),kll[i].v=a[i],kll[i].id=i;

    sort(kll+1,kll+1+m);

    for(int i=1;i<=m;i++){

        if(kll[i].v!=kll[i-1].v) pll[++mar]=kll[i].v;

        a[kll[i].id]=mar;

    }

    int l=1,r=mar;

    while(l<r)

    {

        int mid=l+r>>1;

        if(ck(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d\n",pll[r]);

    return 0;

}