#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

struct Info{

	ll all_sum,left_max,rigt_max,mid_max;
};

int N;
ll input[SIZE];
Info table[8*SIZE];


void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int loc,int value){
	loc += N-1;

	table[loc].all_sum = value;
	table[loc].left_max = value;
	table[loc].rigt_max = value;
	table[loc].mid_max = value;

	if(N == 1)return;

	int parent = (loc-1)/2;

	while(true){

		int left = 2*parent+1,right = 2*parent+2;
		table[parent].all_sum = table[left].all_sum+table[right].all_sum;
		table[parent].left_max = max(table[left].left_max,table[left].all_sum+table[right].left_max);
		table[parent].rigt_max = max(table[right].rigt_max,table[right].all_sum+table[left].rigt_max);
		table[parent].mid_max = max(table[left].rigt_max+table[right].left_max,max(table[left].mid_max,table[right].mid_max));

		if(parent == 0)break;
		else{
			parent = (parent-1)/2;
		}
	}
}

ll query(int search_left,int search_right,int node_id,int node_left,int node_right){

	//今回のノードが検索区間をカバーしていなければ、結果に関係ない値を返す
	if(search_right < node_left || search_left > node_right)return -HUGE_NUM;

	//今回のノードの区間が、検索区間の部分区間である場合、今回のノードの値を返す
	if(search_left <= node_left && search_right >= node_right){
		return table[node_id].mid_max;
	}

	//今回のノードの区間に、一部検索区間と重なっている区間がある場合→再帰的に子どもに尋ねる
	ll left_max = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
	ll right_max = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

	return max(left_max,right_max);
}

int main(){

	int first_N,num_query;
	scanf("%d %d",&first_N,&num_query);

	for(int i = 0; i < first_N; i++){

		scanf("%lld",&input[i]);
	}

	N = 1;
	init(first_N);

	for(int i = 0; i < first_N; i++){

		update(i,input[i]);
	}

	int loc;
	ll value;

	printf("%lld\n",max(0LL,query(0,N,0,0,N)));

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %lld",&loc,&value);
		loc--;

		update(loc,value);
		printf("%lld\n",max(0LL,query(0,N,0,0,N)));
	}

	return 0;
}

