#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int MAXN = 1e6 + 5;
const int offset = 1 << 20;
const int INF = 1e9;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
struct node {
int mini, occ, lazy;
};
struct tournament {
node t[2 * offset];
node merge(node l, node r) {
node res;
res.mini = min(l.mini, r.mini);
res.occ = 0;
if (l.mini == res.mini)
res.occ += l.occ;
if (r.mini == res.mini)
res.occ += r.occ;
res.lazy = l.lazy + r.lazy;
return res;
}
void init(int n) {
for (int i = 0; i < offset; i++)
t[i + offset] = {i < n ? -1 : INF, 1, 0};
for (int i = offset - 1; i >= 0; i--)
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void prop(int x) {
t[x].mini += t[x].lazy;
if (x < offset) {
t[2 * x].lazy += t[x].lazy;
t[2 * x + 1].lazy += t[x].lazy;
}
t[x].lazy = 0;
}
void update(int x, int lo, int hi, int from, int to, int val) {
prop(x);
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
t[x].mini += val;
if (x < offset) {
t[2 * x].lazy += val;
t[2 * x + 1].lazy += val;
}
return;
}
int mid = (lo + hi) / 2;
update(2 * x, lo, mid, from, to, val);
update(2 * x + 1, mid, hi, from, to, val);
t[x] = merge(t[2 * x], t[2 * x + 1]);
}
node query(int x, int lo, int hi, int from, int to) {
prop(x);
if (lo >= to || hi <= from)
return {INF, 1, 0};
if (lo >= from && hi <= to)
return t[x];
int mid = (lo + hi) / 2;
return merge(query(2 * x, lo, mid, from, to), query(2 * x + 1, mid, hi, from, to));
}
void update(int from, int to) {
if (from < to)
update(1, 0, offset, from, to, 1);
else
update(1, 0, offset, to, from, -1);
}
int query(int from, int to) {
node tmp = query(1, 0, offset, from, to);
return tmp.mini ? 0 : tmp.occ;
}
};
int N, H, W;
vector <int> r, c;
vector < vector <int> > mat, mn1, mn2;
tournament T;
bool ok(int x, int y) {
return x > 0 && y > 0 && x <= H && y <= W;
}
void change(int x, int y) {
int old = mn1[x][y];
mn1[x][y] = max(min(mat[x - 1][y], mat[x][y - 1]), mat[x][y]);
T.update(old, mn1[x][y]);
vector <int> adj;
for (int i = 0; i < 4; i++)
adj.push_back(mat[x + dx[i]][y + dy[i]]);
sort(adj.begin(), adj.end());
old = mn2[x][y];
mn2[x][y] = min(adj[1], mat[x][y]);
T.update(mn2[x][y], old);
}
void update_all(int x, int y) {
change(x, y);
for (int i = 0; i < 4; i++)
if (ok(x + dx[i], y + dy[i]))
change(x + dx[i], y + dy[i]);
}
void give_initial_chart(int h, int w, vector <int> R, vector <int> C) {
H = h;
W = w;
r = R;
c = C;
N = H * W;
T.init(N);
mat.resize(H + 2);
mn1.resize(H + 2);
mn2.resize(H + 2);
for (int i = 0; i < H + 2; i++)
mat[i] = mn1[i] = mn2[i] = vector <int> (W + 2, N);
for (int i = 0; i < N; i++) {
r[i]++; c[i]++;
mat[r[i]][c[i]] = mn1[r[i]][c[i]] = mn2[r[i]][c[i]] = i;
}
for (int i = 1; i <= H; i++)
for (int j = 1; j <= W; j++)
change(i, j);
}
int swap_seats(int a, int b) {
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
update_all(r[a], c[a]);
update_all(r[b], c[b]);
return T.query(0, N);
}
