import java.util.*; import java.io.*;

public class CFsolve2 {

public static void main(String[] args) {
    FastScanner input = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);
    int n = input.nextInt();
    int m = input.nextInt();

    long[]arr = new long[n];
    Item[] seg = new Item[4*n];

    for(int i=0;i<n;i++){
        arr[i] = input.nextInt();
        //leaf node holds array elements in tree.
        seg[i+n] = getItem(arr[i]);
    }

    build(n, seg);
    out.println(seg[1].ans);

    while(m-->0){
        int i = input.nextInt();
        int val = input.nextInt();

        //update value in array & segment tree
        arr[i]=val;
        seg[n+i] = getItem(val);

        //fix/update the tree (upwards, leaf to root)
        update(seg, n+i);
        out.println(seg[1].ans);
    }

    out.close();
}

static void build(int n, Item[]seg){
    for(int i=n-1; i>0; i--){
        //same as merge(seg[2*i],seg[2*i+1])
        seg[i] = merge(seg[i<<1], seg[i<<1|1]);
    }
}

static void update(Item[] seg, int i) {
    while (i > 1) {
        i >>>= 1;
        seg[i] = merge(seg[i<<1], seg[i<<1|1]);
    }
}


static Item merge(Item left, Item right){

    Item parent = new Item(0,0,0,0);
    parent.sum = left.sum + right.sum;
    parent.suf = myMax(right.suf, right.sum + left.suf);
    parent.pref = myMax(left.pref, left.sum + right.pref);
    parent.ans = myMax(left.ans, myMax(right.ans,left.suf + right.pref));

    return parent;
}

static class Item{
    long suf,pref,sum,ans;
    Item(long suf, long pref, long sum, long ans){
        this.suf = suf;
        this.pref = pref;
        this.sum = sum;
        this.ans = ans;
    }
}

static Item getItem(long val){
    if(val>0)
        return new Item(val,val,val,val);
    return new Item(0,0,val,0);
}

static long myMin(long l, long r){
    return l<r?l:r;
}
static int myMin(int l, int r){
    return l<r?l:r;
}

static long myMax(long l, long r){
    return l>r?l:r;
}
static int myMax(int l, int r){
    return l>r?l:r;
}



static class FastScanner {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer("");
String next() {
  while (!st.hasMoreTokens())
    try {
      st=new StringTokenizer(br.readLine());
    } catch (IOException e) {
      e.printStackTrace();
    }
  return st.nextToken();
}

int nextInt() {
  return Integer.parseInt(next());
}
int[] readArray(int n) {
  int[] a=new int[n];
  for (int i=0; i<n; i++) a[i]=nextInt();
  return a;
}
byte nextByte(){
  return Byte.parseByte(next());
}
long nextLong() {
  return Long.parseLong(next());
}

} }