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

using namespace std;

long long f[105],X;                 

int main(){

    cin>>X;

    f[0]=2;

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

        f[i]=f[i-1]*2+2;

    cout<<f[X]<<endl;

    return 0;

}

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



int main()

{

	long long n, x = 2, i;



	scanf("%lld", &n); 

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

		x = 2 * (x + 1);

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



	return 0;

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

using namespace std;

long long x,ans=2;

int main()

{

    cin>>x;

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

	{

		ans=ans*2+2;

	}

    cout<<ans<<endl;

}

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



int main()

{

	long long n, x = 2, i;



	scanf("%lld", &n); 

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

		x = 2 * (x + 1);

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



	return 0;

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

#include <cstring>

#include <cstdio>

#include <string>

#include <cmath>

#include <algorithm>

#include <stack>

#include <vector>

#include <map>

using namespace std;

int main()

{

	long long n,i,result=2;

	cin >> n;

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

		result = (result + 1) * 2;

	}

	cout << result << endl;



	return 0;

}

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



int main()

{

	long long n, x = 2, i;



	scanf("%lld", &n); 

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

		x = 2 * (x + 1);

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



	return 0;

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

#include<math.h>

#include<cstdio>

#include<algorithm>

#include<string>

#include<string.h>

using namespace std;

int main() {

	long long x,c=2;

	cin >> x;

	for (int i = 1; i <= x; i++)c = (c + 1) * 2;

	cout << c;

	return 0;

}

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



int main()

{

	long long n, x = 2, i;



	scanf("%lld", &n); 

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

		x = 2 * (x + 1);

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



	return 0;

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

#define pb push_back



using namespace std;



void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)

#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)

#define dbg_ok cerr<<"OK!\n"



typedef pair<int,int> pii;

typedef unsigned long long int ll;

typedef long double ld;



const int DMAX = 1e5+10;



vector <int> vec;

vector <int> arb[DMAX];



int V[DMAX];



ll n;



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(0);



    int t,i,j;



    cin>>n;

    n+=2;

    n=(1LL<<n)-2;

    cout<<n<<'\n';



    return 0;

}


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

#define ll long long

using namespace std;





map<ll,ll> nb;





ll f(ll x){



    if(x<=2) return 0;



    if(nb[x]!=0){

        return nb[x];

    }

    int aux;

    if(x%2==1){

        aux=f((x-1)/2);

    }

    else{

        aux=f((x-2)/2);

    }



    nb[x]=1+aux;



    return nb[x];





}





void cautare(ll stanga,ll dreapta,ll nb,ll &maxim){

    if(stanga>dreapta)

        return;

    ll m=(stanga+dreapta)/2;

    ll miscari=f(m);



    if(miscari==nb){

        maxim=m;

        cautare(m+1,dreapta,nb,maxim);

        return;

    }



    if(miscari>nb){

        cautare(stanga,m-1,nb,maxim);

    }

    else{

        cautare(m+1,dreapta,nb,maxim);

    }

}







int main()

{

    ll x;

    cin>>x;

    ll maxim;

    cautare(2,LONG_MAX,x,maxim);

    cout<<maxim<<"\n";

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

#include<iostream>

using namespace std;

int a,b,c;

int main()

{

	scanf("%1d%1d%1d",&a,&b,&c);

	if(a!=c)cout<<"No\n";

	else cout<<"Yes\n";

}

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

int main(){

    char a,b;

    std::scanf("%c%*c%c",&a,&b);

    std::puts(a==b?"Yes":"No");

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

#include <string>

using namespace std;

int main()

{

    char l,k;

    string a;

    cin>>a;

    l=a[0];

    k=a[2];

    if(l==k)

    {

        cout<<"Yes"<<endl;

    }

    else

    {

        cout<<"No"<<endl;

    }

    return 0;

}


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

int main(){

    char a,b;

    std::scanf("%c%*c%c",&a,&b);

    std::puts(a==b?"Yes":"No");

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

using namespace std;

int main(){

	int a;

	cin>>a;

	if(a%10==a/100)

		cout<<"Yes";

	else

		cout<<"No";

	return 0;

}

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

int main(){

    char a,b;

    std::scanf("%c%*c%c",&a,&b);

    std::puts(a==b?"Yes":"No");

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

using namespace std;

typedef long long ll;

ll minn=1e18+7;

const int maxn=1e5+7;

ll s[maxn];

int main(){

    ll n,a,b,i;

    ll sum=0;

    cin>>n>>a>>b;

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

        cin>>s[i];

    }

    for(i=2;i<=n;i++){

        sum+=min((s[i]-s[i-1])*a,b);

    }

    cout<<sum<<endl;

    return 0;

}


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

#define MIN(a,b) (a)<(b)?(a):(b)

long long n,m,k,c,t,ans;

signed main(){scanf("%lld%lld%lld%lld",&n,&m,&k,&c),n--;while(n--){scanf("%lld",&t),ans+=MIN((t-c)*m,k),c=t;}return printf("%lld\n",ans),0;}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

long long m[1000001];

int main()

{

    long long s=0,n,x,y,i=1;

    cin>>n>>x>>y;

    while(n--){

    	cin>>m[i];

    	if(i>=2){

    		int t=min((m[i]-m[i-1])*x,y);

    		s+=t;

		}

		++i;

	}

    cout<<s<<endl;

    return 0;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

using namespace std;

const int N = 1e5+10;

typedef long long ll;

ll dis[N],a,b,n,low;

int main()

{

	cin>>n>>a>>b;

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

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

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

		low=low+min((dis[i]-dis[i-1])*a,b);

	cout<<low<<"\n";

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

using namespace std;

long long x[100001];//注意定ll，要不然会WA

int main()

{

    long long ans=0,n,a,b,i;

    cin>>n>>a>>b;

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

     cin>>x[i];

    for(i=2;i<=n;i++)//从第一座城市开始

     ans+=min((x[i]-x[i-1])*a,b);//取较小值

    cout<<ans<<endl;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <map>

using namespace std;

typedef long long LL;



LL n,A,B,ans = 0;

LL x[500005] = {0};

 

int main(){

	cin >> n >> A >> B;

	cin >> x[1];

	for(LL i = 2;i <= n;i ++){

		cin >> x[i];

		ans += min((x[i] - x[i - 1]) * A,B);

	}

	cout << ans << endl;

	return 0;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

#include<cstdio>

using namespace std;



int main()

{

	long long len=0,n,a,b,x=0;

	scanf("%lld%lld%lld",&n,&a,&b);

	n--;scanf("%d",&x);

	while (n--)

	{

		long long y;

		scanf("%lld",&y);

		len+=min((y-x)*a,b);

		x=y;

	}

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

	return 0;;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

using namespace std;

long long n,a,b,s[10000000],ans=0;

int main()

{

	cin>>n>>a>>b;

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

		cin>>s[i];

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

	{

		ans+=min(a*(s[i]-s[i-1]),b);

	}

	cout<<ans;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

using namespace std;

long long n,a,b,ans;

long long x[100005];

int main(){

    cin>>n>>a>>b;

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

    	cin>>x[i]; 

	}

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

    	ans+=min(a*(x[i+1]-x[i]),b);

	}

    cout<<ans<<endl;

    return 0; 

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

#include<cstdio>

#include<cmath>

#include<algorithm>



using namespace std;

long long n, a, b, x[100003];

long long ans;

int main()

{

    cin >> n >> a >> b;

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

    {

        cin >> x[i];

    }

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

    {

        if((x[i + 1] - x[i]) * a < b) ans = ans + (x[i + 1] - x[i]) * a;

        else ans = ans + b;

    }

    cout << ans << endl;

    return 0;

}

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

#include <algorithm>



using namespace std;



long long N, A, B, arr[100010], sum = 0;



int main()

{

	scanf("%lld%lld%lld", &N, &A, &B);

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

	{

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

		if (i > 1) sum += min((arr[i] - arr[i - 1]) * A, B);

	}

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

	return 0;

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



int main()

{

	ll n, a, b; cin >> n >> a >> b;

	ll ans = 0;

	ll x[100001] = {};

	repe(i, 1, n) {

		cin >> x[i];

		if (i >= 2) ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



ll x[100001] = {};

int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	ll x[100001] = {};

	repe(i, 1, n) {

		cin >> x[i];

		if (i >= 2) ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



ll x[100001] = {};

int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	ll x[100001] = {};

	repe(i, 1, n) {

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

		if (i >= 2) ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



ll x[100001] = {};

int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	ll x[100001] = {};

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	printf("%lld", ans);

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



ll x[100001] = {};

int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	ll x[100001] = {};

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;

typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)

#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll LL_MAX = (ll)1 << 55;



ll x[100001] = {};

int main()

{

	ll n, a, b;

	scanf("%lld%lld%lld", &n, &a, &b);



	ll ans = 0;

	scanf("%lld", &x[1]);

	repe(i, 2, n) {

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

		ans += min((x[i] - x[i - 1])*a, b);

	}

	cout << ans << endl;

	return 0;

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

using namespace std;

#define H 200000

int v[H+1];



int main(void){

    for(size_t i=0; i<H+1; i++){ v[i] = INT_MAX; }

    int h, w, n, x, y;

    scanf("%d %d %d\n", &h, &w, &n);

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

        scanf("%d %d\n", &x, &y);

        v[x] = y<v[x] ? y : v[x];

    }

    int right = 1;

    for(int x=1; x<h; x++){

        if(v[x+1]<right+1){

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

            return 0;

        }else if(v[x+1]>right+1){

            right++;

        }

    }

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

    return 0;

}


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

#include <limits.h>

#define H 200000

int v[H+1];



int main(void){

    for(size_t i=0; i<H+1; i++){ v[i] = INT_MAX; }

    int h, w, n, x, y;

    scanf("%d %d %d\n", &h, &w, &n);

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

        scanf("%d %d\n", &x, &y);

        v[x] = y<v[x] ? y : v[x];

    }

    int right = 1;

    for(int x=1; x<h; x++){

        if(v[x+1]<right+1){

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

            return 0;

        }else if(v[x+1]>right+1){

            right++;

        }

    }

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

    return 0;

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

#define god dimasi5eks

#pragma GCC optimize("O3")

#define fi first

#define se second

#define pb push_back

#define pf push_front

#define mod 1000000007

#define dancila 3.14159265359

#define eps 1e-9



using namespace std;



typedef long long ll;



int h, w, n;

set<int> s[200002];



int main()

{



    // ifstream cin("a.in");

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    cin >> h >> w >> n;

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

    {

        int a, b;

        cin >> a >> b;

        s[b].insert(a);

    }

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

        s[i].insert(h+1);

    int ans = (1<<20);

    int col = 1;

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

    {

        ans = min(ans, (*s[col].lower_bound(i+1)) - 1);

        if(col < w && *s[col+1].lower_bound(i+1) != i+1)

            ++col;

    }

    cout << ans << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8699794964983456x):
//minamoto

#include<bits/stdc++.h>

#define R register

#define pb push_back

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

const int N=2e5+5;

vector<int>pos[N];int vis[N];

int n,m,k,res,t,mx;

int main(){

	scanf("%d%d%d",&n,&m,&k);

	for(R int i=1,x,y;i<=k;++i)scanf("%d%d",&x,&y),pos[y].pb(x);

	fp(i,1,m)pos[i].pb(n+1),sort(pos[i].begin(),pos[i].end());

	res=pos[1][0]-1,t=0;

	fp(i,2,m){

		mx=0;

		for(auto v:pos[i]){

			if(v<=i+t||vis[v-1])vis[v]=1,cmax(mx,v);

			else{cmin(res,v-1);break;}

		}

		cmax(t,mx-i+1);

	}

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

	return 0;

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

#include<algorithm>

#include<vector>

#include<string>

#include<set>

using namespace std;



#define INF ( 1 << 30 )

typedef multiset<int,int>::iterator itr;



int main()

{

  int N, Q;

  int stmp[1000000], comp[1000000], a;

  char buff[1024];

  scanf( "%d %d", &N, &Q);

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

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

    comp[i] = stmp[i];

  }

  sort( comp, comp + N);



  multiset< int > sym;

  while(Q--){

    scanf("%s %d", buff, &a);

    if(*buff == 'A'){ //ADD



      sym.insert(stmp[a - 1]);



    } else if(*buff == 'R'){ //REMOVE

      try{

        sym.erase( sym.lower_bound(stmp[a - 1]));

      }catch( ... ){}

    } else { //CHECK



      int left = 0, right = INF;

      while(left != right){

        int center = ( left + right ) / 2;

        int pre = 0, BAN = 0;

        for(itr it = sym.begin() ; it != sym.end() ; it++ ){

          int p = distance( comp,lower_bound( comp, comp + N, *it - center));

          BAN += max( p - pre, 0);

          pre = distance( comp, upper_bound( comp, comp + N, *it));

        }

        BAN += max( N - pre, 0);

        if(BAN <= a) right = center;

        else left = center + 1;

      }

      if( left != INF) printf("%d\n", left);

      else puts("NA");



    }

  }

  return false;

}

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

using namespace std;



int N, Q;

vector< int > values, s;

vector< int > reader;



bool calc(int value, int a){ //reader[i]以下reader[i]-value以上

  int pre = 0, ng = 0;

  for(int i = 0; i < reader.size(); i++){

    int pos = lower_bound( values.begin(), values.end(), reader[i] - value) - values.begin(); //reader[i]-value以上

    ng += max( 0, pos - pre);

    pre = upper_bound( values.begin(), values.end(), reader[i]) - values.begin(); //reader[i]以下

  }

  ng += max< int >( 0, N - pre);

  return (ng <= a);

}



int main(){



  scanf("%d %d", &N, &Q);

  values.resize(N), s.resize(N);



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

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

    values[i] = s[i];

  }

  sort(values.begin(), values.end());



  while(Q--){

    char query[100];

    int a;

    scanf("%s %d", query, &a);



    if(strcmp(query,"ADD") == 0){



      a--;

      reader.push_back(s[a]);

      sort( reader.begin(), reader.end());



    } else if(strcmp(query,"REMOVE") == 0){



      a--;

      reader.erase(lower_bound( reader.begin(), reader.end(), s[a]));



    } else {

      int row = 0, high = 1000000001;

      while(high != row){

        int mid = (row + high) >> 1;

        if(calc(mid, a)) high = mid;

        else row = mid + 1;

      }



      if(row == 1000000001) puts("NA");

      else printf("%d\n", row);

    }



  }



}