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 Item getItem(long val){
    if(val>0)
        return new Item(val,val,val,val);
    return new Item(0,0,val,0);
}

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 long myMax(long l, long r){
    return l>r?l:r;
}

My Output: 5 11 8

Correct Output: 8 11 7