#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const int SZ = 1 << 20;
const int INF = 1e9 + 9;
int mini[2 * SZ], cnt[2 * SZ], lazy[2 * SZ];
void pass(int u) {
if (u < SZ) {
lazy[2 * u + 1] += lazy[u];
lazy[2 * u] += lazy[u];
}
mini[u] += lazy[u];
lazy[u] = 0;
}
void compute(int u) {
if (mini[2 * u] < mini[2 * u + 1]) {
mini[u] = mini[2 * u], cnt[u] = cnt[2 * u];
} else if (mini[2 * u + 1] < mini[2 * u]) {
mini[u] = mini[2 * u + 1], cnt[u] = cnt[2 * u + 1];
} else {
mini[u] = mini[2 * u], cnt[u] = cnt[2 * u] + cnt[2 * u + 1];
}
}
void update(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) return;
if (s <= l && r <= e) {
lazy[u] += v;
return pass(u);
}
int m = (l + r) / 2;
update(s, e, v, l, m, 2 * u);
update(s, e, v, m, r, 2 * u + 1);
compute(u);
}
vector<vi> val;
void change(int i, int j, int delta) {
vi value = {val[i][j], val[i + 1][j], val[i][j + 1], val[i + 1][j + 1]};
sort(all(value));
update(value[0], value[1], delta);
update(value[2], value[3], delta);
}
vi r, c;
void give_initial_chart(int H, int W, vi R, vi C) {
r = R, c = C;
val.assign(H + 2, vi(W + 2, SZ));
forn(i, H * W) val[R[i] + 1][C[i] + 1] = i;
forn(i, 2 * SZ) mini[i] = INF, cnt[i] = 0;
vi delta(SZ + 1, 0);
forn(i, H + 1) forn(j, W + 1) {
vi value = {val[i][j], val[i + 1][j], val[i][j + 1], val[i + 1][j + 1]};
sort(all(value));
delta[value[0]]++;
delta[value[1]]--;
delta[value[2]]++;
delta[value[3]]--;
}
int pref = 0;
forn(i, H * W) {
pref += delta[i];
mini[i + SZ] = pref;
cnt[i + SZ] = 1;
}
dforsn(i, 1, SZ) compute(i);
}
int swap_seats(int a, int b) {
forn(x, 2) forn(y, 2) {
change(r[a] + x, c[a] + y, -1);
change(r[b] + x, c[b] + y, -1);
}
swap(r[a], r[b]);
swap(c[a], c[b]);
val[r[a] + 1][c[a] + 1] = a;
val[r[b] + 1][c[b] + 1] = b;
forn(x, 2) forn(y, 2) {
change(r[a] + x, c[a] + y, 1);
change(r[b] + x, c[b] + y, 1);
}
assert(mini[1] == 4);
return cnt[1];
}
