#include<ctime>#include<cstdio>#include<cstdlib>#include<algorithm>#define lc k<<1#define rc k<<1|1#define EF if(ch==EOF) return x;using namespace std;const int N=1e5+5;const int inf=2e9;typedef long long ll;int n,Q,ans,a[N],mx[N];ll sum[N<<2];bool tag[N<<2];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;EF;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}void build(int k,int l,int r){    if(l==r){        sum[k]=mx[l];        return ;    }    int mid=l+r>>1;    build(lc,l,mid);    build(rc,mid+1,r);    sum[k]=sum[lc]+sum[rc];}void pushdown(int k,int l,int r){    if(!tag[k]||l==r) return ;    int mid=l+r>>1;    sum[lc]=sum[k]/(r-l+1)*(mid-l+1);    sum[rc]=sum[k]/(r-l+1)*(r-mid);    tag[lc]=tag[rc]=1;tag[k]=0;}void change(int k,int l,int r,int x,int y,int v){    if(l==x&&r==y){        sum[k]=1LL*(r-l+1)*v;        tag[k]=1;        return ;    }    pushdown(k,l,r);    int mid=l+r>>1;    if(y<=mid) change(lc,l,mid,x,y,v);    else if(x>mid) change(rc,mid+1,r,x,y,v);    else change(lc,l,mid,x,mid,v),change(rc,mid+1,r,mid+1,y,v);    sum[k]=sum[lc]+sum[rc];}ll query(int k,int l,int r,int p){    if(l==r) return sum[k];    pushdown(k,l,r);    int mid=l+r>>1;    if(p<=mid) return query(lc,l,mid,p);    else return query(rc,mid+1,r,p);//    sum[k]=sum[lc]+sum[rc];}void ord(){    int Max=-inf;ans=0;    for(int j=1;j<=n;j++){        Max=max(Max,a[j]);        ans+=Max;    }    printf("%d\n",ans);    for(int i=1,x,y;i<=Q;i++){        x=read();y=read();        a[x]+=y;        int Max=-inf;ans=0;        for(int j=1;j<=n;j++){            Max=max(Max,a[j]);            ans+=Max;        }        printf("%d\n",ans);    }}int main(){    n=read();    for(int i=1;i<=n;i++) a[i]=read();Q=read();    if(n<=2000){        ord();        return 0;    }    mx[0]=-inf;    for(int i=1;i<=n;i++) mx[i]=max(mx[i-1],a[i]);    build(1,1,n);printf("%I64d\n",sum[1]);    for(int i=1,x,y;i<=Q;i++){        x=read();y=read();        a[x]+=y;        int l=x,r=n,pos=0;        while(l<=r){            int mid=l+r>>1;            if(query(1,1,n,mid)<a[x]) l=mid+1,pos=mid;            else r=mid-1;        }        if(pos) change(1,1,n,x,pos,a[x]);        printf("%I64d\n",sum[1]);    }    return 0;}