#include <iostream>
#include <map>
using namespace std;

struct node
{
	int x,y;
	node(int x1,int y1)
	{
		x=x1;
		y=y1;
	}
};

int main() {

	int n,m;
	cin>>n>>m;

	int a[n];
	int indices[n+1];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		indices[a[i]]=i;
	}
	
	int ans=1;
	for(int j=1;j<n;j++)
	{
		if(indices[j] > indices[j+1])
		{
			ans++;
		}
	}
	//cout<<"ans="<<ans<<endl;	
	
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		
		x--;
		y--;
		
		map<int,map<int,int> > updatedPairs;
		if(a[x]+1 <=n)
		{
			updatedPairs[a[x]][a[x]+1]=1;
		}
		if(a[x]-1 >=0)
		{
			updatedPairs[a[x]-1][a[x]]=1;
		}
		if(a[y]+1 <=n)
		{
			updatedPairs[a[y]][a[y]+1]=1;
		}
		if(a[y]-1 >=0)
		{
			updatedPairs[a[y]-1][a[y]]=1;
		}
		
		
		for(auto it=updatedPairs.begin();it!=updatedPairs.end();it++)
		{
			map<int,int> Map = it->second;
			for(auto it2=Map.begin();it2!=Map.end();it2++)
			{
				ans-=(indices[it->first] > indices[it2->first]);
			}
		}
		
		//cout<<"ans="<<ans<<endl;
		
		int temp = a[x];
		a[x] = a[y];
		a[y] = temp;
		
		indices[a[x]]=x;
		indices[a[y]]=y;
		
		for(auto it=updatedPairs.begin();it!=updatedPairs.end();it++)
		{
			map<int,int> Map = it->second;
			for(auto it2=Map.begin();it2!=Map.end();it2++)
			{
				ans+=(indices[it->first] > indices[it2->first]);
			}
		}
		
		cout<<ans<<endl;
	}
	
	

	return 0;
}