//In the name of God
#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)
struct rect{
ll mnx, mny, mxx, mxy;
};
ll h, w;
pll p[maxn];
rect seg[maxn << 2];
rect mrg(rect l, rect r){
rect m = {min(l.mnx, r.mnx), min(l.mny, r.mny), max(l.mxx, r.mxx), max(l.mxy, r.mxy)};
return m;
}
void bld(ll id, ll s, ll e){
if(e - s == 1){
seg[id] = {p[s].F, p[s].S, p[s].F, p[s].S};
return;
}
ll mid = (s + e) >> 1;
bld(lc, s, mid);
bld(rc, mid, e);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
void upd(ll id, ll s, ll e, ll x){
if(x < s || e <= x) return;
if(e - s == 1){
seg[id] = {p[s].F, p[s].S, p[s].F, p[s].S};
return;
}
ll mid = (s + e) >> 1;
upd(lc, s, mid, x);
upd(rc, mid, e, x);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
rect get(ll id, ll s, ll e, ll x){
if(x >= e) return seg[id];
ll mid = (s + e) >> 1;
if(x <= mid) return get(lc, s, mid, x);
return mrg(get(lc, s, mid, x), get(rc, mid, e, x));
}
rect get(ll x){
return get(1, 0, h * w, x);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
for(ll i = 0; i < H * W; i++){
p[i] = Mp(R[i], C[i]);
}
bld(1, 0, H * W);
return;
}
inline ll cal(rect rct){
return (rct.mxx - rct.mnx + 1) * (rct.mxy - rct.mny + 1);
}
ll solve(){
ll x = 1;
ll ans = 1;
while(x != h * w){
ll y = cal(get(x));
if(y == x){
ans++;
x++;
}
else x = y;
}
return ans;
}
int swap_seats(int a, int b){
swap(p[a], p[b]);
upd(1, 0, h * w, a);
upd(1, 0, h * w, b);
return solve();
}
