#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
vector<int>A[1000007];
const int pot=1<<20;
int seg[2*pot+7];
int lzy[2*pot+7];
int ile[2*pot+7];
void push(int v)
{
seg[2*v]+=lzy[v];
seg[2*v+1]+=lzy[v];
lzy[2*v]+=lzy[v];
lzy[2*v+1]+=lzy[v];
lzy[v]=0;
}
void ins(int v,int a,int b,int l,int r,int x)
{
if(a<=l&&b>=r)
{
seg[v]+=x;
lzy[v]+=x;
return ;
}
if(r<a||l>b) return ;
push(v);
ins(2*v,a,b,l,(l+r)/2,x);
ins(2*v+1,a,b,(l+r)/2+1,r,x);
seg[v]=min(seg[2*v],seg[2*v+1]);
ile[v]=0;
if(seg[v]==seg[2*v]) ile[v]+=ile[2*v];
if(seg[v]==seg[2*v+1]) ile[v]+=ile[2*v+1];
}
void upd(int i,int j,int x)
{
vector<int>V={A[i][j],A[i+1][j],A[i][j+1],A[i+1][j+1]};
sort(all(V));
ins(1,V[0],V[1]-1,1,pot,x);
ins(1,V[2],V[3]-1,1,pot,x);
}
void S(int i,int j,int x)
{
upd(i-1,j-1,x);
upd(i,j-1,x);
upd(i-1,j,x);
upd(i,j,x);
}
vector<int>x,y;
void give_initial_chart(int h,int w,vector<int>R,vector<int>C)
{
x=R,y=C;
for(int i=0;i<=h+1;i++) A[i].resize(w+2,h*w+1);
for(int i=0;i<h*w;i++) A[x[i]+1][y[i]+1]=i+1;
for(int i=1;i<=h*w;i++) ile[i+pot-1]=1;
for(int i=h*w+1;i<=pot;i++) seg[i+pot-1]=inf;
for(int i=pot-1;i>0;i--)
{
seg[i]=min(seg[2*i],seg[2*i+1]);
ile[i]=ile[2*i]+ile[2*i+1];
}
for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) upd(i,j,1);
}
int swap_seats(int a, int b)
{
S(x[a]+1,y[a]+1,-1);
S(x[b]+1,y[b]+1,-1);
swap(A[x[a]+1][y[a]+1],A[x[b]+1][y[b]+1]);
swap(x[a],x[b]);
swap(y[a],y[b]);
S(x[a]+1,y[a]+1,1);
S(x[b]+1,y[b]+1,1);
return ile[1];
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
cout<<swap_seats(0, 5)<<endl;
cout<<swap_seats(0, 5)<<endl;
return 0;
}*/
