#include<bits/stdc++.h>
using namespace std;

#define int long long

int solve1(vector<int>&v){
	int N=v.size();
	int s=min_element(v.begin(),v.end())-v.begin();
	int ans=0;
	for(int i=0,j=0;i<N;i++){
		if(v[s]<v[(s+1)%N]){
			j++;
		}
		else if(j){
			ans+=(j+1)/2;
			j=0;
		}
		s=(s+1)%N;
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,Q;
	cin>>N>>Q;
	vector<int>v(N),n(N),p(N);
	for(int i=0;i<N;i++){
		cin>>v[i];
		n[i]=i==N-1?0:i+1;
		p[i]=i==0?N-1:i-1;
	}
	int s=min_element(v.begin(),v.end())-v.begin();
	map<int,int>z;
	for(int i=0,j=0;i<N;i++){
		if(v[s]<v[n[s]]){
			j++;
		}
		else if(j){
			z.emplace((s-j+N)%N,s);
			j=0;
		}
		s=n[s];
	}
	int ans=0;
	for(auto[x,y]:z){
		ans+=((y-x+N)%N+1)/2;
	}
	auto ins=[&](int s,int e){
		if(s==e)return;
		ans+=((e-s+N)%N+1)/2;
		z.emplace(s,e);
	};
	cout<<ans<<' ';
	for(int i=0;i<Q;i++){
		int x;
		cin>>x>>v[x];
		if(!z.empty()){
			auto t=z.upper_bound(x);
			t=t==z.begin()?prev(z.end()):prev(t);
			int s=t->first,e=t->second;
			if(x>=s&&x<=e||x>=s&&s>e||e>=x&&s>e){
				z.erase(t);
				ans-=((e-s+N)%N+1)/2;
				if(x==s&&x==e){
				}
				else if(x==s){
					s=n[s];
					ins(s,e);
				}
				else if(x==e){
					e=p[e];
					ins(s,e);
				}
				else{
					ins(s,p[x]);
					ins(n[x],e);
				}
			}
		}
		int s=v[p[x]]<v[x]?p[x]:x;
		int e=v[x]<v[n[x]]?n[x]:x;
		if(z.empty()){
			ins(s,e);
		}
		else{
			auto t=z.upper_bound(x);
			if(t==z.end()){
				t=z.begin();
			}
			if(t->first==e){
				auto[ss,ee]=*t;
				t=z.erase(t);
				ans-=((ee-ss+N)%N+1)/2;
				e=ee;
			}
			if(!z.empty()){
				t=t==z.begin()?prev(z.end()):prev(t);
				if(t->second==s){
					auto[ss,ee]=*t;
					t=z.erase(t);
					ans-=((ee-ss+N)%N+1)/2;
					s=ss;
				}
			}
			ins(s,e);
		}
		cout<<ans<<' ';
	}
	cout<<'\n';
	return 0;
}