stablegradients/pie-gem5-pairs huggingface dataset:
// 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.136539104818944x):
#include<cstdio>

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	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 (l == 1 && r == 2 * n - 1) return (a[n] >= x) ^ ((n + 1) & 1);

	if (l == 1) return a[r] >= x;

	if (r == 2 * n - 1) return a[l] >= x;

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#define maxn 200005

int arr[maxn],n,seq[maxn],rank[maxn],ref[maxn];



int cmp(int a,int b){return arr[a]<arr[b];}



int check(int x){

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

	int mid=(n/2)+1;

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

		seq[i]=(ref[i]>x);

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

	}//printf("\n");

	if (seq[mid]==seq[mid-1]||seq[mid]==seq[mid+1]) return seq[mid];

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

		if (seq[mid-i]==seq[mid-i-1]||seq[mid+i]==seq[mid+i+1]) return seq[mid-i];

	return seq[1];

}



int main(){

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

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

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

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

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

		rank[i]=i;

	}if (n==1) {printf("%d ",arr[1]);return 0;}

	std::sort(rank+1,rank+n+1,cmp);

	for (int i=1;i<=n;++i) ref[rank[i]]=i;

//	for (int i=1;i<=n;++i) printf("%d ",ref[i]); printf("\n");

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

	while (l<r){

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

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

		else {r=mid;ans=mid;}

	}printf("%d",arr[rank[ans]]);

	return 0;

}




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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include <cstdlib>

#include <cstdio>

#define N 400011

using namespace std;

int b[N],len,n,a[N],cnt[N],ans,maxx,minn;

int judge(int avr){

	b[0]=-1;

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

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

		if(b[i]==b[i-1]) cnt[i]=cnt[i-1]+1;

		else cnt[i]=1;

	}

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

		if(cnt[n+i]>=2) return b[n+i];

		if(cnt[n-i]>=2) return b[n-i];

	}

	return b[1];

}

void bin(){

	int head=minn,tail=maxx,mid;

	while(head<=tail){

		mid=(head+tail)/2;

		if(judge(mid)){

			ans=mid;

			head=mid+1;

		}

		else tail=mid-1;

	}

}

int main(){

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

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

	for(int i=1;i<=len;i++) scanf("%d",&a[i]),minn=min(minn,a[i]),maxx=max(maxx,a[i]);

	bin();

	printf("%d",ans);

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include<cmath>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<ctime>

using namespace std;

const int N=200010;

int n,a[N];

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

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

bool check(int x)

{

	int i;

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

	{

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

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

	}

	return judge2(1,1,x);

}

int main()

{

    int i,j,l,r,mid,ans;

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

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

    while(l<=r)

    {

    	mid=l+r>>1;

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

    	else l=mid+1;

	}

	cout<<ans<<endl;

    return 0;	

} 

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include <cstdio>

using namespace std;

int n,a[200005],f[200005];

bool check(int x)

{

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

	{	

	  if(a[i]>x)f[i]=1;

	  else f[i]=0;

	}

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

    {

    	 if(f[n-i]==f[n-i+1])

    	 {

    	 	if(f[n-i]==0)return 0;

    	 	else return 1;

		 }

    	 if(f[n+i]==f[n+i-1])

    	 {

    	    if(f[n+i]==0)return 0;

    	 	else return 1;	

		 }

    }

    if(f[1]==0)return 0;

    return 1;

}

int main()

{



	int maxx=0;

	cin>>n;

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

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

	    if(a[i]>maxx)maxx=a[i];

	}

	int l=1,r=maxx;

	while(l<r)

	{

		int mid=l+r>>1;

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

		else r=mid;

	}

	cout<<l<<endl;

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include <cstdio>

#include <iostream>

using namespace std;

int read();



int N, x[200005], st[200005], a[200005];

int work() {

    int m = N / 2 + 1, res = a[m], l = m, r = m;

    a[0] = a[1], a[N + 1] = a[N];

    for (; l >= 1 && a[l] != a[l - 1] && a[r] != a[r + 1]; --l, ++r) res ^= 1;

    return res;

}



int main() {

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

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

    N = read() * 2 - 1;

    for (int i = 1; i <= N; ++i) st[i] = x[i] = read();

    sort(st + 1, st + 1 + N);

    int l = 1, r = N, res = r;

    while (l <= r) {

        int mid = l + r >> 1;

        for (int i = 1; i <= N; ++i) a[i] = x[i] > st[mid];

        if (!work())

            r = mid - 1, res = mid;

        else

            l = mid + 1;

    }

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

    return 0;

}

int read() {

    int x = 0, f = 1;

    char c = getchar();

    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = getchar();

    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();

    return x * f;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

using namespace std;

int a[400005],n;

int small(int i,int j,int k)

{

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

}

int big(int i,int j,int k)

{

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

}

int check(int k)

{

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

	{

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

		{

			return 1;

		}

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

		{

			return 0;

		}

	}

	return small(1,1,k);

}

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)==1)

		{

			r=mid;

		}else

		{

			l=mid+1;

		}

	}

	cout<<r;

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

using namespace std;

int a[200005],n;

bool b[200005];

inline bool pd(int x)

{

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

	{

		if(a[i]>=x)

			b[i]=1;

		else

			b[i]=0;

	}

	b[0]=b[1];

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

		return b[n];

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

	{

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

			return b[i];

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

			return b[n+n-i];

	}

	return b[1];

}

int main(int argc, char** argv) {

	cin >> n;

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

		cin >> a[i];

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

	while(l<=r)

	{

		int md=(l+r)/2;

		if(pd(md))

		{

			l=md+1;

			ans=max(ans,md);

		}

		else

			r=md-1;

	}

	cout << ans << endl;

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include <stdio.h>

using namespace std;

const int N = 1e5 + 9;

int a[N << 1], f[N << 1], n;

bool check(int x){

    int sum = 0;

    for(int i = 1; i < 2*n; i++) f[i] = a[i] >= x, sum += f[i];

    for(int i = n-1; i >= 1; i--){

        int xx = 2*n-i;

        if(f[xx] == f[xx - 1]) return f[xx]; 

        if(f[i] == f[i+1]) return f[i]; 

    }

    return sum >= n;

}

int erfen(int l, int r){

    while(l < r){

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

        if(check(mid)) l = mid;

        else r = mid - 1;

    }

    return l;

}

int main(){

    scanf("%d", &n);

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

    printf("%d", erfen(1, 2*n-1));

    return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

using namespace std;

int a[200005],n;

bool b[200005];

inline bool pd(int x){

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

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

	b[0]=b[1];

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

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

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

	}

	return b[1];

}

int main(int argc, char** argv) {

	cin >> n;

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

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

	while(l<=r){

		int md=(l+r)/2;

		if(pd(md))

			l=md+1,ans=max(ans,md); 

		else

			r=md-1;

	}

	cout << ans;

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

using namespace std;

int a[200005],n;

bool b[200005];

bool pd(int x){

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

	b[0]=b[1];

	for(int i=n;i<=n+n-1;i++){if(b[i]==b[i+1])return b[i];if(b[n+n-i]==b[n+n-i-1])return b[n+n-i];}

	return b[1];

}

int main(){

cin>>n;

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

int l=1,r=n*2,A=0,md;

while(l<=r){

md=(l+r)/2;

if(pd(md)) l=md+1,A=md;else r=md-1;

}cout<<A;}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include <stdio.h>

#include <algorithm>



using namespace std;



int num[500005];

int vis[500005];

int t;



int abs1(int x)

{

   if (x>=0)

      return x;

   else

      return -x;

}

int check(int x)

{

   x%=2;

   if (x==0)

      return (vis[t]^1);

   else

      return vis[t];

}



int main()

{

cin>>t;

for (int a=1;a<=2*t-1;a++)

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

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

int mid;

int k;

while (l<=r)

{

   mid=(l+r)>>1;

   k=-1;

   for (int a=1;a<=2*t-1;a++)

      if (num[a]>=mid)

         vis[a]=1;

      else

         vis[a]=0;

   pair<int,int> flag1;

   pair<int,int> flag2;

   flag1.first=-1;

   flag2.first=-1;

   for (int a=t;a>=2;a--)

      if (vis[a]==vis[a-1])

      {

	     flag1.second=vis[a];

         flag1.first=a;

         break;

	  }

   for (int a=t;a<2*t-1;a++)

      if (vis[a]==vis[a+1])

      {

         flag2.second=vis[a];

         flag2.first=a;

         break;

	  }

   if (flag1.first!=-1||flag2.first!=-1)

   {

      if (abs1(flag1.first-t)>abs1(flag2.first-t))

         k=flag2.second;

      else

         k=flag1.second;

   }

   if (k==-1)

      k=check(t);

   if (k==0)

      r=mid-1;

   if (k==1)

      l=mid+1;

}

cout<<r;

	return 0;

}

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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

#include<cmath>

#include<cstdio>

#include<stdlib.h>

#include<algorithm>

#include<cstring>

#include<vector>

#define MAXN 100005

using namespace std;

int a[2*MAXN],n;

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 ef(int l,int r)

{

	int mid;

	while(l<r)

	{

		mid=(l+r)>>1;

		if(check(mid))

			r=mid;

		else

			l=mid+1;

	}

	return l;

}

int main()

{

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

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

	scanf("%d",&n);

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

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

	printf("%d",ef(1,2*n-1));

    return 0;

}


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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

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

using namespace std;

#define il inline

#define gc getchar()

#define mp make_pair

#define P pair<int,int>

#define ri register int

#define rb register bool

#define rc register char

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)



const int N=2e5+10;

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

bool b[N];



il int read()

{

	rc ch=gc;ri x=0;rb y=1;

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

	if(ch=='-')ch=gc,y=0;

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

	return y?x:-x;

}

il bool chck(){rp(i,2,n)if(b[i]==b[i-1])return 0;return 1;}

il bool check(ri dat)

{

	rp(i,1,n)b[i]=(a[i]>dat);ri mid=(n+1)>>1;if(chck())return b[1];

	rp(i,1,mid-1){if(b[mid+i]==b[mid+i-1])return b[mid+i];if(b[mid-i]==b[mid-i+1])return b[mid-i];}

}



int main()

{

	//freopen("2165.in","r",stdin);freopen("2165.out","w",stdout);

	n=r=read()*2-1;rp(i,1,n)a[i]=read();

	while(l<r){ri mid=(l+r)>>1;if(!check(mid))r=mid;else l=mid+1;}printf("%d",l);

	return 0;

}


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

const int N=2e5+3,INF=1e9;

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

inline bool Check(int g){

	int tmp=0,l=n+n,r=0;

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

	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];

	if(tmp==n+n-2)return!b[1];

	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];

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

	  if(b[i]==b[i-1]){l=i;break;}

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

	  if(b[i]==b[i+1]){r=i;break;}

	if(l==n+n)return!b[r];

	if(!r)return!b[l];

	return!b[n-l>r-n?r:l];

}

int main(){

	int l,r,m;

	scanf("%d",&n);

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

	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;

	printf("%d",l);

	return 0;

}