#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
using pll=pair<ll,ll>;
constexpr ll LINF=(1LL<<62)-(1LL<<31);
#include "seats.h"
template<class T,auto op,auto e>
struct SegTree{
vector<T> val;
int size;
SegTree(int sz){
size=sz;
val.resize(size*2,e());
}
void set(int pos,T v){
pos+=size;
val[pos]=v;
while(pos>1){
pos/=2;
val[pos]=op(val[pos*2],val[pos*2+1]);
}
}
T prod(int lf,int ri){
lf+=size;
ri+=size;
T ret_lf=e();
T ret_ri=e();
while(lf<ri){
if(lf&1){
ret_lf=op(ret_lf,val[lf]);
lf++;
}
if(ri&1){
ri--;
ret_ri=op(val[ri],ret_ri);
}
lf/=2;
ri/=2;
}
return op(ret_lf,ret_ri);
}
};
pll mx(pll x,pll y){
return {min(x.first,y.first),max(x.second,y.second)};
}
pll e(){
return {LINF,-LINF};
}
SegTree<pll, mx, e> x(1000000);
SegTree<pll, mx, e> y(1000000);
vector<int> r,c;
int h,w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h=H;
w=W;
r=R;
c=C;
rep(i,H*W){
x.set(i,pll(R[i],R[i]));
}
rep(i,H*W){
y.set(i,pll(C[i],C[i]));
}
}
int get(int i){
pll xs=x.prod(0,i+1);
pll ys=y.prod(0,i+1);
return (xs.second-xs.first+1)*(ys.second-ys.first+1);
}
int swap_seats(int a, int b) {
if(a>b)swap(a,b);
swap(r[a],r[b]);
swap(c[a],c[b]);
x.set(a,{r[a],r[a]});
x.set(b,{r[b],r[b]});
y.set(a,{c[a],c[a]});
y.set(b,{c[b],c[b]});
int ans=1;
int now=1;
int lst=0;
while(now<h*w){
int ok=h*w-1,ng=lst;
while(ok-ng>1){
int mid=(ok+ng)>>1;
if(get(mid)>now){
ok=mid;
}
else{
ng=mid;
}
}
now=get(ok);
lst=ok;
if(now==get(now-1)){
ans++;
}
}
return ans;
}
