Note.ms

#include<bits/stdc++.h>
using namespace std;
int n,q,s[2005],t[2005];
long long a[1000005];
bool check(int x,int j){
    int y=0;
    for(int i=1;i<=j;i++){
        if(x>s[i]) y++;
    }
    return x-y<=s[j+1];
}
bool check1(int x,int j){
    int y=1;
    for(int i=1;i<=j;i++){
        if(x>s[i]) y++;
    }
    return x-y<=t[j+1];
}
void solve(){
	cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>s[i]>>t[i];
       	int l=s[i],r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid,i-1)){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        s[i]=r;
        l=t[i],r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(check1(mid,i-1)){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        t[i]=r;
        cout<<s[i]<<' '<<t[i]<<'\n';
        a[t[i]]+=a[s[i]];
        a[s[i]]=-12;
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=-12){
            cout<<a[i]<<' ';
        }
    }
}
int main(){
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;

Note.ms/gjd