#include<bits/stdc++.h>
using namespace std;
vector<bool> good;
vector<int> r;
vector<int> c;
int n;
const int INF=1e9+7;
struct node{
int maxi = 0;
int mini = INF;
};
node zero={0, INF};
struct segtree{
vector<node> tree;
void init(int n){
tree.assign(n*4, zero);
}
node merge(node a, node b){
a.maxi = max(a.maxi, b.maxi);
a.mini = min(a.mini, b.mini);
return a;
}
node update(int l,int r, int v, int x, int val){
if(x<l || r<=x) return tree[v];
if(l+1==r){
return tree[v]={val, val};
}
int m=l+(r-l)/2;
return tree[v]=merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
}
node query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return zero;
if(ql<=l && r<=qr){
return tree[v];
}
int m=l+(r-l)/2;
return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
segtree segr;
segtree segc;
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
r=R;
c=C;
n=h*w;
good.assign(n, 0);
segr.init(n);
segc.init(n);
for(int i=0; i<n; i++){
segr.update(0, n, 0, i, r[i]);
segc.update(0, n, 0, i, c[i]);
auto valr=segr.query(0, n, 0, 0, i+1);
auto valc=segc.query(0, n, 0, 0, i+1);
int size = (valr.maxi - valr.mini + 1) * (valc.maxi - valc.mini + 1);
if(size == i+1){
good[i]=true;
}
}
}
int swap_seats3(int a, int b){
int oldr = r[a];
segr.update(0, n, 0, a, r[b]);
segr.update(0, n, 0, b, oldr);
swap(r[a], r[b]);
int oldc=c[a];
segc.update(0, n, 0, a, c[b]);
segc.update(0, n, 0, b, oldc);
swap(c[a], c[b]);
good.assign(n, false);
int cnt=0;
for(int i=0; i<n; i++){
auto valr=segr.query(0, n, 0, 0, i+1);
auto valc=segc.query(0, n, 0, 0, i+1);
int size = (valr.maxi - valr.mini +1) * (valc.maxi - valc.mini +1);
if(size == i+1){
good[i]=true;
cnt++;
}
i = max(i, size -2);
}
return cnt;
}
int swap_seats(int a, int b) {
return swap_seats3(a, b);
}
