#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
struct event{
int id,val,type;
inline friend bool operator < (event fr,event sc){
return fr.id<sc.id;
}
};
int n,m,minx,maxx,miny,maxy,ans,pt;
pair<int,int> w[MAXN];
set<int> row[MAXN],col[MAXN];
vector<int> curr;
vector<event> special;
void add_positions(){
special.clear();
curr={};
for(int i=0;i<n;i++){
while(!curr.empty() and *row[i].begin()<*row[curr.back()].begin()){
curr.pop_back();
}
curr.push_back(i);
}
for(int i:curr)special.push_back({*row[i].begin(),i,1});
curr={};
for(int i=n-1;i>=0;i--){
while(!curr.empty() and *row[i].begin()<*row[curr.back()].begin()){
curr.pop_back();
}
curr.push_back(i);
}
for(int i:curr)special.push_back({*row[i].begin(),i,1});
curr={};
for(int i=0;i<m;i++){
while(!curr.empty() and *col[i].begin()<*col[curr.back()].begin()){
curr.pop_back();
}
curr.push_back(i);
}
for(int i:curr)special.push_back({*col[i].begin(),i,2});
curr={};
for(int i=m-1;i>=0;i--){
while(!curr.empty() and *col[i].begin()<*col[curr.back()].begin()){
curr.pop_back();
}
curr.push_back(i);
}
for(int i:curr)special.push_back({*col[i].begin(),i,2});
sort(special.begin(),special.end());
}
int swap_seats(int x,int y){
x++; y++;
row[w[x].first].erase(x);
col[w[x].second].erase(x);
row[w[y].first].erase(y);
col[w[y].second].erase(y);
swap(w[x],w[y]);
row[w[x].first].insert(x);
col[w[x].second].insert(x);
row[w[y].first].insert(y);
col[w[y].second].insert(y);
add_positions(); ans=0;
special.push_back({n*m+1,0,0});
minx=miny=n+m; maxx=maxy=-1;
for(int i=0;i<special.size()-1;i++){
if(special[i].type==1){
minx=min(minx,special[i].val);
maxx=max(maxx,special[i].val);
}else{
miny=min(miny,special[i].val);
maxy=max(maxy,special[i].val);
}
if(special[i].id==special[i+1].id)continue;
if((maxx-minx+1)*(maxy-miny+1)>=special[i].id and (maxx-minx+1)*(maxy-miny+1)<=special[i+1].id){
ans++;
}
}
return ans;
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C){
n=H; m=W;
for(int i=1;i<=n*m;i++){
w[i]={R[i-1],C[i-1]};
row[w[i].first].insert(i);
col[w[i].second].insert(i);
}
}
/*
int main(){
give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1,1, 2, 2});
cout<<swap_seats(0, 5)<<"\n"<<swap_seats(0, 5)<<"\n";
}
*/
