#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
vp v;
ll n,h,w;
vvi grid;
vi tate,yoko;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;w=W;n=H*W;
rep(i,n)v.pb(R[i],C[i]);
grid=vvi(h,vi(w));
rep(i,n)grid[v[i].fi][v[i].se]=i;
tate=vi(w,inf);
yoko=vi(h,inf);
rep(i,h)rep(j,w){
chmin(tate[j],grid[i][j]);
chmin(yoko[i],grid[i][j]);
}
}
int swap_seats(int a, int b) {
swap(v[a],v[b]);
swap(grid[v[a].fi][v[a].se],grid[v[b].fi][v[b].se]);
tate[v[a].se]=tate[v[b].se]=inf;
yoko[v[a].fi]=yoko[v[b].fi]=inf;
rep(i,h){
chmin(tate[v[a].se],grid[i][v[a].se]);
chmin(tate[v[b].se],grid[i][v[b].se]);
}
rep(i,w){
chmin(yoko[v[a].fi],grid[v[a].fi][i]);
chmin(yoko[v[b].fi],grid[v[b].fi][i]);
}
vi tl=tate,tr=tate,yu=yoko,yd=yoko;
rep(i,w-1)chmin(tl[i+1],tl[i]);
for(int i=w-1;i>0;i--)chmin(tr[i-1],tr[i]);
rep(i,h-1)chmin(yu[i+1],yu[i]);
for(int i=h-1;i>0;i--)chmin(yd[i-1],yd[i]);
int ans=1;
vi cur={v[0].se,v[0].se,v[0].fi,v[0].fi};
while(true){
ll s=(cur[1]-cur[0]+1)*(cur[3]-cur[2]+1);
if(s==n)break;
ll mi=inf,t;
if(cur[0]>0&&chmin(mi,tl[cur[0]-1]))t=0;
if(cur[1]<w-1&&chmin(mi,tr[cur[1]+1]))t=1;
if(cur[2]>0&&chmin(mi,yu[cur[2]-1]))t=2;
if(cur[3]<h-1&&chmin(mi,yd[cur[3]+1]))t=3;
if(mi==s)ans++;
if(t==0)cur[0]--;
if(t==1)cur[1]++;
if(t==2)cur[2]--;
if(t==3)cur[3]++;
}
return ans;
}
