#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+;

const int inf=2e9;

typedef long long ll;

int n,Q,ans,a[N],mx[N];

ll sum[N<<];bool tag[N<<];

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;EF;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';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>>;

    build(lc,l,mid);

    build(rc,mid+,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>>;

    sum[lc]=sum[k]/(r-l+)*(mid-l+);

    sum[rc]=sum[k]/(r-l+)*(r-mid);

    tag[lc]=tag[rc]=;tag[k]=;

}

void change(int k,int l,int r,int x,int y,int v){

    if(l==x&&r==y){

        sum[k]=1LL*(r-l+)*v;

        tag[k]=;

        return ;

    }

    pushdown(k,l,r);

    int mid=l+r>>;

    if(y<=mid) change(lc,l,mid,x,y,v);

    else if(x>mid) change(rc,mid+,r,x,y,v);

    else change(lc,l,mid,x,mid,v),change(rc,mid+,r,mid+,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>>;

    if(p<=mid) return query(lc,l,mid,p);

    else return query(rc,mid+,r,p);

//    sum[k]=sum[lc]+sum[rc];

}

void ord(){

    int Max=-inf;ans=;

    for(int j=;j<=n;j++){

        Max=max(Max,a[j]);

        ans+=Max;

    }

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

    for(int i=,x,y;i<=Q;i++){

        x=read();y=read();

        a[x]+=y;

        int Max=-inf;ans=;

        for(int j=;j<=n;j++){

            Max=max(Max,a[j]);

            ans+=Max;

        }

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

    }

}

int main(){

    n=read();

    for(int i=;i<=n;i++) a[i]=read();Q=read();

    if(n<=){

        ord();

        return ;

    }

    mx[]=-inf;

    for(int i=;i<=n;i++) mx[i]=max(mx[i-],a[i]);

    build(,,n);printf("%I64d\n",sum[]);

    for(int i=,x,y;i<=Q;i++){

        x=read();y=read();

        a[x]+=y;

        int l=x,r=n,pos=;

        while(l<=r){

            int mid=l+r>>;

            if(query(,,n,mid)<a[x]) l=mid+,pos=mid;

            else r=mid-;

        }

        if(pos) change(,,n,x,pos,a[x]);

        printf("%I64d\n",sum[]);

    }

    return ;

}