//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "seats.h"
const int maxn = 1e3+10;
int n;
int h,w;
pii pos[maxn*maxn];
set <int> r[maxn],c[maxn];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
rep(i,0,H*W) pos[i] = {R[i],C[i]}, r[R[i]].insert(i),c[C[i]].insert(i);
n = H*W;
h = H, w=W;
}
int swap_seats(int a, int b) {
int ret = 0;
r[pos[a].fi].erase(a),c[pos[a].se].erase(a);
r[pos[b].fi].erase(b),c[pos[b].se].erase(b);
swap(pos[a],pos[b]);
r[pos[a].fi].insert(a),c[pos[a].se].insert(a);
r[pos[b].fi].insert(b),c[pos[b].se].insert(b);
vector <pii> minx,maxx,miny,maxy;
rep(i,0,h) {
int cur = (*r[i].begin()); //first appearance of row i
while (!maxx.empty() and maxx.back().fi > cur) maxx.pop_back();
maxx.pb({cur,i});
}
for (int i=h-1;i>=0;i--) {
int cur = (*r[i].begin());
while (!minx.empty() and minx.back().fi > cur) minx.pop_back();
minx.pb({cur,i});
}
rep(i,0,w) {
int cur = (*c[i].begin()); //first appearance of row i
while (!maxy.empty() and maxy.back().fi > cur) maxy.pop_back();
maxy.pb({cur,i});
}
for (int i=w-1;i>=0;i--) {
int cur = (*c[i].begin());
while (!miny.empty() and miny.back().fi > cur) miny.pop_back();
miny.pb({cur,i});
}
reverse(ALL(minx));reverse(ALL(miny));reverse(ALL(maxx));reverse(ALL(maxy));
int lst = -1,lstarea=-233;
int val0,val1,val2,val3;
while (SZ(minx)+SZ(miny)+SZ(maxx)+SZ(maxy)>0) {
int cur = mod;
if (!minx.empty()) cur = min(cur,minx.back().fi);
if (!miny.empty()) cur = min(cur,miny.back().fi);
if (!maxx.empty()) cur = min(cur,maxx.back().fi);
if (!maxy.empty()) cur = min(cur,maxy.back().fi);
// debug(cur);
if (lstarea>=lst and lstarea<cur) ret++;
if (!minx.empty() and minx.back().fi==cur) val0 = minx.back().se,minx.pop_back();
if (!maxx.empty() and maxx.back().fi==cur) val1 = maxx.back().se,maxx.pop_back();
if (!miny.empty() and miny.back().fi==cur) val2 = miny.back().se,miny.pop_back();
if (!maxy.empty() and maxy.back().fi==cur) val3 = maxy.back().se,maxy.pop_back();
lstarea = (val1-val0+1)*(val3-val2+1)-1;
lst = cur;
}
if (lstarea>=lst and lstarea<n) ret++;
return ret;
}
