#include <stdio.h>

 #include <stdlib.h>

 #include <algorithm>

 #include <string.h>

 const int N=;

 using namespace std;

 struct node

 {

     int l,r,sum,minsum,maxsum;

     int lmax,rmax,lmin,rmin;

 } Tree[*N];

 int a[N];

 void pushup(int rt)

 {

     int l = *rt;

     int r = *rt+;

     Tree[rt].sum=Tree[l].sum+Tree[r].sum;

     Tree[rt].minsum=min(min(Tree[l].minsum,Tree[r].minsum),Tree[l].rmin+Tree[r].lmin);

     Tree[rt].maxsum=max(max(Tree[l].maxsum,Tree[r].maxsum),Tree[l].rmax+Tree[r].lmax);

     Tree[rt].lmax=max(Tree[l].lmax,Tree[l].sum+Tree[r].lmax);

     Tree[rt].rmax=max(Tree[r].rmax,Tree[r].sum+Tree[l].rmax);

     Tree[rt].lmin=min(Tree[l].lmin,Tree[l].sum+Tree[r].lmin);

     Tree[rt].rmin=min(Tree[r].rmin,Tree[r].sum+Tree[l].rmin);

 }

 void build(int l,int r,int rt)

 {

     Tree[rt].l = l;

     Tree[rt].r = r;

     if (l==r)

     {

         Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=a[r];

         Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=a[r];

         return ;

     }

     int mid = (l+r)>>;

     build(l,mid,*rt);

     build(mid+,r,*rt+);

     pushup(rt);

 }

 void update(int pos,int val,int rt)

 {

     if (Tree[rt].l==Tree[rt].r)

     {

         Tree[rt].sum=Tree[rt].minsum=Tree[rt].maxsum=val;

         Tree[rt].lmax=Tree[rt].rmax=Tree[rt].lmin=Tree[rt].rmin=val;

         return ;

     }

     int mid=(Tree[rt].l+Tree[rt].r)>>;

     if (pos<=mid)

         update(pos,val,*rt);

     else

         update(pos,val,*rt+);

     pushup(rt);

 }

 int main()

 {

     int n,m,pos,val;

     scanf("%d",&n);

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

     {

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

     }

     build(,n,);

     scanf("%d",&m);

     while(m--)

     {

         scanf("%d%d",&pos,&val);

         update(pos,val,);

         if(Tree[].sum==Tree[].maxsum)

         {

             printf("%d\n",Tree[].sum-Tree[].minsum);

         }

         else

         {

             printf("%d\n",max(Tree[].maxsum,Tree[].sum-Tree[].minsum));

         }

     }

     return ;

 }