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

#include<algorithm>

using namespace std;

int a[200005];

int b[200005];

int main(void)

{

    int n,mx1,mx2;

    cin >> n;

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

    {

        cin >> a[i];

        b[i]=a[i];

    }

    sort(b,b+n);

    mx1=b[n-1];

    mx2=b[n-2];

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

    {

        if(a[i]==mx1)

            cout << mx2 << '\n';

        else cout << mx1 << '\n';

    }

    return 0;

}


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

#include<algorithm>

using namespace std;

int a[200005];

int lm[200005];

int rm[200005];

int main(void)

{

    int n;

    scanf("%d" ,&n);

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

    {

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

        lm[i]=max(lm[i-1],a[i-1]);

    }

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

        rm[i]=max(rm[i+1],a[i+1]);

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

        printf("%d\n" ,max(lm[i],rm[i]));

    return 0;

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

using namespace std;

int a[200005];

int lmax[200005];

int rmax[200005];

int main(void)

{

    int n;

    cin >> n;

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

        cin >> a[i];

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

        lmax[i]=max(lmax[i-1],a[i-1]);

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

        rmax[i]=max(rmax[i+1],a[i+1]);

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

        cout << max(lmax[i],rmax[i]) << '\n';

    return 0;

}


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

#include<algorithm>

using namespace std;

int a[200005];

int lm[200005];

int rm[200005];

int main(void)

{

    int n;

    scanf("%d" ,&n);

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

    {

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

        lm[i]=max(lm[i-1],a[i-1]);

    }

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

        rm[i]=max(rm[i+1],a[i+1]);

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

        printf("%d\n" ,max(lm[i],rm[i]));

    return 0;

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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <vector>

#include <stdio.h>

#include <set>

#include <map>

#include <unordered_set>

#include <unordered_map>

#include <queue>

#include <ctime>

#include <cassert>

#include <complex>

#include <string>

#include <cstring>

#include <chrono>

#include <random>

#include <queue>

#include <bitset>

#include <iomanip>

using namespace std;





typedef long long ll;

//typedef pair<string, int> pii;

//typedef pair<ll, ll> pll;

typedef vector<int> vi;

//typedef vector<pii> vpi;

typedef vector<vi> vvi;

typedef pair <int,int> pii;

typedef pair <int,pii> pi;

#define fi first

#define se second

#define pb push_back

#define szz(x) (int)x.size()

#define rep(i,n) for(int i=0;i<n;i++)

#define all(x) x.begin(),x.end()

#define sv(v) sort(v.begin(),v.end())

#define floop(a,n) for(int i=a; i<n; i++)

#define max3(a,b,c) max(a, max(b,c))

#define max4(a,b,c,d) max(a, max(b,max(c,d)))

#define min3(a,b,c) min(a, min(b,c))

#define min4(a,b,c,d) min(a, min(b,min(c,d)))

vector <int> v;

string int_to_string(int a){return to_string(a);}

int string_to_int(string s){stringstream x(s);int a=0; x>>a; return a;}

//long long int gcd(long long int a, long long int b){if(a%b==0)return b;return gcd(b, a%b);}

//long long int lcm(long long int a, long long int b){return (a*b)/gcd(a, b);}



//long long int factorial(int a){if(a==0)return 1;elsereturn a*factorial(a-1);}







int main()

{

    map <string,int>mp;

    

    int a,b,c,max=0;

    string s,p;

    

    cin >> a;

    while(a--)

    {

        cin >> s;

        mp[s]++;

    }

    

    cin >> a;

    while(a--)

    {

        cin >> s;

        mp[s]--;

    }

    

    for(auto it = mp.cbegin(); it!=mp.cend(); ++it)

    {

        if(it -> second > max)

            max = it -> second;

    }

    

    cout << max << endl;

    

}




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

#include<string.h>

char ch[205][11],str[11];

int s[205];

int main()

{

	int a,b,k=0;

	scanf("%d",&a);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]++;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]++;

			k++;

		}

	}

	scanf("%d",&b);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]--;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]--;

			k++;

		}

	}

	int max=0;

	for(int i=0;i<k;i++)if(s[i]>max)max=s[i];

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

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

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <map>

using namespace std;



int main(){

    int n,m;

    map <string,int> ans;

    cin>>n;

    getchar();

    string St;

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

        cin>>St;

        ans[St] ++;

    }

    cin>>m;

    getchar();

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

        cin>>St;

        ans[St]--;

    }

    int result = 0;

    map<string,int> ::iterator iter;

    for (iter = ans.begin();iter!=ans.end();iter++){

        result = max(result,iter->second);

    }

    cout<<result<<endl;

}


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

#include<string.h>

char ch[205][11],str[11];

int s[205];

int main()

{

	int a,b,k=0;

	scanf("%d",&a);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]++;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]++;

			k++;

		}

	}

	scanf("%d",&b);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]--;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]--;

			k++;

		}

	}

	int max=0;

	for(int i=0;i<k;i++)if(s[i]>max)max=s[i];

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

}
// Slower C++ solution:
//https://blog.csdn.net/hesorchen

// #include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <map>

#include <cmath>

using namespace std;

#define ll long long

#define endl "\n"

#define mod 1000000007

#define MAX 200005

map<string, int> p;

string a[100005];

int ct;

int main()

{

    int n, m;

    cin >> n;

    string temp;

    while (n--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]++;

    }

    cin >> m;

    while (m--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]--;

    }

    int ans = 0;

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

        ans = max(ans, p[a[i]]);

    cout << ans << endl;



    return 0;

}


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



using namespace std;



typedef long long ll;



double getTime() {

  return clock() / (double) CLOCKS_PER_SEC;

}



void read() {};



template<typename T, typename... Args>

void read(T& a, Args&... args) {

  cin >> a;

  read(args...);

}



void print() {};



template <typename T, typename... Args>

void print(T a, Args... args) {

  cout << a << " \n"[sizeof...(args) == 0];

  print(args...);

}



int main() {

  int n; cin >> n;

  map <string, int> cnt1, cnt2;

  while(n--) {

    string s; cin >> s;

    cnt1[s]++;

    cnt2[s] = 0;

  }

  int m; cin >> m;

  while(m--) {

    string s; cin >> s;

    cnt2[s]++;

  }

  int mx = 0;

  for(auto x : cnt1) {

    mx = max(mx, cnt1[x.first] - cnt2[x.first]);

  }

  print(mx);

}
// Slower C++ solution:
//https://blog.csdn.net/hesorchen

// #include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <map>

#include <cmath>

using namespace std;

#define ll long long

#define endl "\n"

#define mod 1000000007

#define MAX 200005

map<string, int> p;

string a[100005];

int ct;

int main()

{

    int n, m;

    cin >> n;

    string temp;

    while (n--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]++;

    }

    cin >> m;

    while (m--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]--;

    }

    int ans = 0;

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

        ans = max(ans, p[a[i]]);

    cout << ans << endl;



    return 0;

}


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

using namespace std;

#define ll long long

vector<ll>vi;

vector<ll> :: iterator vt;

ll arr[200009];

int main()

{

    ll n,t,x,y,z,j,i,k,m,flag =0,maxi=LONG_LONG_MIN ,mini=LONG_LONG_MAX,sum=0,c=0;

    map<string,ll>mp;

    map<string,ll> :: iterator mt;

    string s, ss;

    cin>>n;

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

    {

        cin>>s;

        mp[s]++;

    }

    cin>>m;

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

    {

        cin>>s;

        mp[s]--;

    }

    for(mt = mp.begin() ;mt!= mp.end() ;mt++)

    {

        maxi = max(mt->second,maxi);

    }

    if(maxi<0)

        maxi = 0;

    cout<<maxi<<endl;

}
// Slower C++ solution:
//https://blog.csdn.net/hesorchen

// #include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <map>

#include <cmath>

using namespace std;

#define ll long long

#define endl "\n"

#define mod 1000000007

#define MAX 200005

map<string, int> p;

string a[100005];

int ct;

int main()

{

    int n, m;

    cin >> n;

    string temp;

    while (n--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]++;

    }

    cin >> m;

    while (m--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]--;

    }

    int ans = 0;

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

        ans = max(ans, p[a[i]]);

    cout << ans << endl;



    return 0;

}


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

using namespace std;

int main()

{

    long long n,i,j,k,l,m,x,y;

    string s1,s2,s3;

    map<string ,int>m1;

    map<string ,int>m2;

    map<string ,int>::iterator it;

    cin>>n;

    cin.ignore();

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

    {

        cin>>s1;

        m1[s1]++;

    }

    cin>>m;

    cin.ignore();

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

    {

        cin>>s2;

        m2[s2]++;

    }

    x=-10000;

    for(it=m1.begin();it!=m1.end();it++)

    {

        k=m1[it->first];

        l=m2[it->first];

        y=k-l;

        if(y>x)

        {

            x=y;

        }



    }

    if(x<0)

    {

        x=0;

    }

    cout<<x<<endl;

    return 0;

}
// Slower C++ solution:
//https://blog.csdn.net/hesorchen

// #include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <map>

#include <cmath>

using namespace std;

#define ll long long

#define endl "\n"

#define mod 1000000007

#define MAX 200005

map<string, int> p;

string a[100005];

int ct;

int main()

{

    int n, m;

    cin >> n;

    string temp;

    while (n--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]++;

    }

    cin >> m;

    while (m--)

    {

        cin >> temp;

        a[ct++] = temp;

        p[temp]--;

    }

    int ans = 0;

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

        ans = max(ans, p[a[i]]);

    cout << ans << endl;



    return 0;

}


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

        Author: Prokash

                CSE48, JU



*/



#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int main()

{

    FAST;

    map<string,int>blue,red;

    map<string,int>::iterator it;

    ll n,m,t;

    cin>>n;

    while(n--)

    {

        string str;

        cin>>str;

        blue[str]++;

    }

    cin>>m;

    while(m--)

    {

        string str;

        cin>>str;

        red[str]++;

        blue[str]--;

    }

    int ans=INT_MIN;

    for(it=blue.begin();it!=blue.end();it++)

    {

        ans=max(ans,(it->second));

    }

    if(ans>=0)

    {

        cout<<ans<<endl;

    }

    else

    {

        cout<<0<<endl;

    }

    return 0;

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

#include <string>

#include <map>

using namespace std;

int max(int a, int b) {

    if (a > b) return a;

    return b;

}

typedef long long ll;

map<string, int> m1, m2;

int main() {

    int N, M;

    cin >> N;

    string str;

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

        cin >> str;

        m1[str] += 1;

    }

    cin >> M;

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

        cin >> str;

        m2[str] += 1;

    }

    int res = 0;



    for (auto it = m1.begin(); it != m1.end(); ++it) {

        str = (*it).first;

        if (m1[str] > m2[str]) {

            res = max((m1[str] - m2[str]), res);

        }

    }



    cout << res;

    return 0;

}

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

#include<string.h>

char ch[205][11],str[11];

int s[205];

int main()

{

	int a,b,k=0;

	scanf("%d",&a);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]++;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]++;

			k++;

		}

	}

	scanf("%d",&b);

	getchar();

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

	{

		scanf("%s",str);

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(strcmp(ch[j],str)==0)

			{

				flag=1;

				s[j]--;

				break;

			}

		}

		if(flag==0)

		{

			strcpy(ch[k],str);

			s[k]--;

			k++;

		}

	}

	int max=0;

	for(int i=0;i<k;i++)if(s[i]>max)max=s[i];

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

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

#define  ll   long long int

#define  sz   20010



using namespace std;





string ss[sz];

string sx[sz];

map<string,ll>mp;

map<string,ll>mp2;



set<string>st;

set<string> :: iterator it;



int main()

{





    ll n,m,i,j,a,b,p;



    cin>>n;



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

    {

        cin>>ss[i];

        mp2[ss[i]]++;

        st.insert(ss[i]);

    }





    cin>>m;



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

    {

        cin>>sx[i];

        mp[sx[i]]++;

        st.insert(sx[i]);

    }



    ll c=0;





    for(it=st.begin();it!=st.end();it++)

    {

        string s=*it;

        a=mp[s];

        b=mp2[s];

        ll x=(b-a);

        c=max(c,x);

    }



    cout<<c<<endl;



    return 0;

}




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

#define ll long long int

using namespace std;



int main()

{

    ll n,m,i,j;

    cin>>n;

    string a;

    map<string,ll>ma;

    map<string,ll>:: iterator it;

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

    {

        cin>>a;

        ma[a]++;

    }

    cin>>m;

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

    {

        cin>>a;

        ma[a]--;

    }

    ll x=-999999999999;

    for(it=ma.begin(); it!=ma.end(); it++)

    {

        x=max(x,it->second);

    }

    if(x<0)

    {

        cout<<0<<endl;

    }

    else{

    cout<<x<<endl;}

    return 0;

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

using namespace std;

#define N 333333

#define rev(a) reverse(a+1,a+n+1)

#define ll long long

 

int n,t,a[N];

long long s[N],l[N],r[N],f[N],g[N],h[N],q[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

ll sum(int n){return (ll)n*(n+1)/2;} 

double slope(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&slope(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&slope(q[t-1],q[t])<=slope(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void calc(ll *f){

	int i;q[t=1]=0;init_s();

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

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

 

void solve(int x,int y){

	if (x==0&&y==n) for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

	if (x==y) return;

	int mid=(x+y)/2;t=0;

	for (int i=x;i<=mid;i++){

		g[i]=l[i]+1ll*i*(i-1)/2+s[i];

		push(i);

	}

	for (int i=mid+1;i<=y;i++){

		pop(i);

		h[i]=g[q[t]]-1ll*i*q[t]+1ll*i*(i+1)/2-s[i]+r[i+1];

	}

	for (int i=y-1;i>mid;i--) h[i]=max(h[i],h[i+1]);

	for (int i=mid+1;i<=y;i++) f[i]=max(f[i],h[i]);

	solve(x,mid);solve(mid+1,y);

}

 

int main(){

	n=read();

	for (int i=1;i<=n;i++) a[i]=read(),f[i]=-1e18;

	calc(l);rev(a);calc(r);rev(a);rev(r);

	solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (int m=read();m;m--){

		int p=read(),x=read();

		printf("%lld\n",max(l[p-1]+r[p+1],a[p]+f[p]-x));

	}

}

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

#include<algorithm>

#define ll long long

#define rev(a) reverse(a+1,a+n+1)

using namespace std;

const int N=3e5+5,inf=1e9;

int n,i,a[N];

ll s[N],g[N],l[N],r[N],f[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

void write(ll x){if (x>9) write(x/10);putchar(x%10+48);}

ll sum(int n){return (ll)n*(n+1)/2;}

int t,q[N];

double cal(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&cal(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&cal(q[t-1],q[t])<=cal(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void init(ll *f){

	int i;q[t=1]=0;init_s();

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

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

ll w[N];

void work(int x,int y){

	if (x==y) return;int i,m=x+y>>1;t=0;

	for (i=x;i<=m;i++) g[i]=l[i]+sum(i-1)+s[i],push(i);

	for (;i<=y;i++) pop(i),

		w[i]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];

	for (f[y]=max(f[y],w[y]),i=y-1;i>m;i--)

		f[i]=max(f[i],w[i]=max(w[i],w[i+1]));

	work(x,m);work(m+1,y);

}

int main(){

	for (n=read(),i=1;i<=n;i++) a[i]=read(),f[i]=-inf;

	init(l);rev(a);init(r);rev(a);rev(r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (i=read();i--;putchar('\n')){

		int x=read(),k=read();

		write(max(l[x-1]+r[x+1],f[x]+a[x]-k));

	}	

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

using namespace std;

#define N 333333

#define rev(a) reverse(a+1,a+n+1)

#define ll long long

 

int n,t,a[N];

long long s[N],l[N],r[N],f[N],g[N],h[N],q[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

ll sum(int n){return (ll)n*(n+1)/2;} 

double slope(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&slope(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&slope(q[t-1],q[t])<=slope(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void calc(ll *f){

	int i;q[t=1]=0;init_s();

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

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

 

void solve(int x,int y){

	if (x==y) return;

	int mid=(x+y)/2;t=0;

	for (int i=x;i<=mid;i++){

		g[i]=l[i]+1ll*i*(i-1)/2+s[i];

		push(i);

	}

	for (int i=mid+1;i<=y;i++){

		pop(i);

		h[i]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];

	}

	for (int i=y-1;i>mid;i--) h[i]=max(h[i],h[i+1]);

	for (int i=mid+1;i<=y;i++) f[i]=max(f[i],h[i]);

	solve(x,mid);solve(mid+1,y);

}

 

int main(){

	n=read();

	for (int i=1;i<=n;i++) a[i]=read(),f[i]=-1e18;

	calc(l);rev(a);calc(r);rev(a);rev(r);

	init_s();solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	init_s();solve(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (int m=read();m;m--){

		int p=read(),x=read();

		printf("%lld\n",max(l[p-1]+r[p+1],a[p]+f[p]-x));

	}

}

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

#include<algorithm>

#define ll long long

#define rev(a) reverse(a+1,a+n+1)

using namespace std;

const int N=3e5+5,inf=1e9;

int n,i,a[N];

ll s[N],g[N],l[N],r[N],f[N];

int read(){

	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());

	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;

}

void write(ll x){if (x>9) write(x/10);putchar(x%10+48);}

ll sum(int n){return (ll)n*(n+1)/2;}

int t,q[N];

double cal(int x,int y){return (double)(g[x]-g[y])/(x-y);}

void pop(int x){for (;t>1&&cal(q[t-1],q[t])<=x;t--);}

void push(int x){

	for (;t>1&&cal(q[t-1],q[t])<=cal(q[t],x);t--);q[++t]=x;

}

void init_s(){for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];}

void init(ll *f){

	int i;q[t=1]=0;init_s();

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

		pop(i);f[i]=max(f[i-1],f[q[t]]+sum(i-q[t])-s[i]+s[q[t]]);

		g[i]=f[i]+sum(i-1)+s[i];push(i);

	}

}

ll w[N];

void work(int x,int y){

	if (x==y) return;int i,m=x+y>>1;t=0;

	for (i=x;i<=m;i++) g[i]=l[i]+sum(i-1)+s[i],push(i);

	for (;i<=y;i++) pop(i),

		w[i]=l[q[t]]+r[i+1]+sum(i-q[t])-s[i]+s[q[t]];

	for (f[y]=max(f[y],w[y]),i=y-1;i>m;i--)

		f[i]=max(f[i],w[i]=max(w[i],w[i+1]));

	work(x,m);work(m+1,y);

}

int main(){

	for (n=read(),i=1;i<=n;i++) a[i]=read(),f[i]=-inf;

	init(l);rev(a);init(r);rev(a);rev(r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	init_s();work(0,n);rev(a);rev(f);rev(l);rev(r);swap(l,r);

	for (i=read();i--;putchar('\n')){

		int x=read(),k=read();

		write(max(l[x-1]+r[x+1],f[x]+a[x]-k));

	}	

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

#include <vector>

#include <string>

#include <algorithm>

#include <stdio.h>

#include <cmath>

using namespace std;



int to_int(string s){

    int number = 0;

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

        number *= 10;

        number += s[i] - '0';

    }

    return number;

}



string to_str(int n){

    string s;

    while(n!=0){

        s += n % 10 + 48;

        n /= 10;

    }

    reverse(s.begin(),s.end());

    return s;

}



bool isLeapYear(int year)

{

    if(((year % 4 == 0 ) && (year % 100 != 0)) || (year % 400 == 0))

        return true;

    else

        return false;

}



bool isPrime(int n)

{

    if (n == 2)

        return true;

    if ((n & 1)==0)

        return false;

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

        if (n%i == 0)

            return false;

    }



    return true;

}



/*#define row 5001

#define col 10000



int arr[row][col];



void fib()

{

    arr[0][0] = 0;

    arr[1][0] = 1;

    for(int i=2;i<row;i++){

        for(int j=0;j<col;j++){

            if(arr[i-1][j] + arr[i-2][j] == 0)

                continue;

            arr[i][j] += arr[i-1][j] + arr[i-2][j];

            if(arr[i][j] > 9){

                arr[i][j+1] = arr[i][j]/10;

                arr[i][j] %= 10;

            }

        }

    }

}*/



int main()

{

    int a, b, c;

    cin >> a >> b >> c;

    if((b-a) == (c-b))

        cout << "YES" << endl;

    else

        cout << "NO" << endl;



    return 0;

}


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



int main ()

{

	int a=0,b=0,c=0;

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

	

	if(b-a==c-b)

	{

		printf("YES\n");

	}

	else if (b-a!=c-b)

	{

		printf("NO\n");

	}

	

	

	

	return 0;

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

using namespace std;



int main ()

{

    int a, b, c;



    cin>>a>>b>>c;



    if (b-a==c-b)

    {

        cout<<"YES";

    }

    else

    {

        cout<<"NO";

    }

}


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



int main ()

{

	int a=0,b=0,c=0;

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

	

	if(b-a==c-b)

	{

		printf("YES\n");

	}

	else if (b-a!=c-b)

	{

		printf("NO\n");

	}

	

	

	

	return 0;

}