#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
int n,h,w;
vector<array<int,2>> v;
vector<int> ar,br,ac,bc;
int res=0;
const int N=1000;
set<int> row[N];
vector<int> rowmn(N,N*N);
set<int> col[N];
vector<int> colmn(N,N*N);
int ok(int i){return ((br[i]-ar[i]+1)*(bc[i]-ac[i]+1)==i+1);}
void give_initial_chart(int nh,int nw,vector<int> r,vector<int> c)
{
h=nh;
w=nw;
n=h*w;
v.assign(n,{0,0});
for(int i=0;i<n;i++) v[i]={r[i],c[i]};
ar.assign(n,v[0][0]);
br.assign(n,v[0][0]);
ac.assign(n,v[0][1]);
bc.assign(n,v[0][1]);
res=ok(0);
for(int i=1;i<n;i++)
{
ar[i]=min(ar[i-1],v[i][0]);
br[i]=max(br[i-1],v[i][0]);
ac[i]=min(ac[i-1],v[i][1]);
bc[i]=max(bc[i-1],v[i][1]);
res+=ok(i);
}
if(h<=1000&&w<=1000)
{
for(int i=0;i<h;i++) row[i].insert(h*w);
for(int i=0;i<w;i++) col[i].insert(h*w);
for(int i=0;i<n;i++)
{
row[v[i][0]].insert(i);
col[v[i][1]].insert(i);
}
for(int i=0;i<h;i++) rowmn[i]=(*row[i].begin());
for(int i=0;i<w;i++) colmn[i]=(*col[i].begin());
}
}
int swap_seats(int a,int b)
{
if(h>1000||w>1000)
{
if(a>b) swap(a,b);
swap(v[a],v[b]);
for(int i=a;i<=b;i++)
{
res-=ok(i);
ar[i]=min((i>0?ar[i-1]:n),v[i][0]);
br[i]=max((i>0?br[i-1]:0),v[i][0]);
ac[i]=min((i>0?ac[i-1]:n),v[i][1]);
bc[i]=max((i>0?bc[i-1]:0),v[i][1]);
res+=ok(i);
}
return res;
}
else
{
if(a>b) swap(a,b);
row[v[a][0]].erase(a);
col[v[a][1]].erase(a);
row[v[b][0]].erase(b);
col[v[b][1]].erase(b);
swap(v[a],v[b]);
row[v[a][0]].insert(a);
col[v[a][1]].insert(a);
row[v[b][0]].insert(b);
col[v[b][1]].insert(b);
rowmn[v[a][0]]=(*row[v[a][0]].begin());
rowmn[v[b][0]]=(*row[v[b][0]].begin());
colmn[v[a][1]]=(*col[v[a][1]].begin());
colmn[v[b][1]]=(*col[v[b][1]].begin());
int r=0;
int now=0;
// int cnt=0;
// cout << "in" << endl;
vector<array<int,2>> cd,ef;
for(int i=0;i<h;i++) cd.push_back({rowmn[i],i});
for(int i=0;i<w;i++) ef.push_back({colmn[i],i});
sort(cd.begin(),cd.end());
sort(ef.begin(),ef.end());
int cdidx=0;
int efidx=0;
int c=h,d=-1,e=w,f=-1;
while(now<n)
{
// cout << now << " ";
while(cdidx<h&&cd[cdidx][0]<=now)
{
int t=cd[cdidx++][1];
c=min(c,t);
d=max(d,t);
}
while(efidx<w&&ef[efidx][0]<=now)
{
int t=ef[efidx++][1];
e=min(e,t);
f=max(f,t);
}
// cout << "[" << c << "," << d << "," << e << "," << f << "] ";
// cout.flush();
if((d-c+1)*(f-e+1)==now+1) r++;
now=max(now+1,(d-c+1)*(f-e+1)-1);
// cnt++;
}
// assert(cnt<=2*(w+h));
// cout << endl;
return r;
}
}
//int main()
//{
//
// return 0;
//}
