#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int Z = 1<<20;
struct node{
node()
{
sum = min = 0; cnt = 1;
}
node(int v)
{
sum = min = v; cnt = 1;
}
int sum, min, cnt;
node operator *(const node &t) const{
node res;
res.sum = sum + t.sum;
if (min < sum + t.min) res.min = min;
else res.min = sum + t.min;
res.cnt = 0;
if (res.min == min) res.cnt += cnt;
if (res.min == sum + t.min) res.cnt += t.cnt;
return res;
}
void add(int p)
{
sum += p;
min += p;
}
} IT[Z*2];
int N,A[1001001]; bool chk[1001001]; int H,W; vector<int> R,C;
void upd(int x)
{
x /= 2;
while (x){
IT[x] = IT[x*2] * IT[x*2+1];
x /= 2;
}
}
set<int> ups;
void add(int i, int p, bool up = true)
{
if (p > 0){
if (chk[i]) return;
chk[i] = 1;
}
else{
if (!chk[i]) return;
chk[i] = 0;
}
int x = R[i], y = C[i];
int dx[5] = {0,1,0,-1,0};
int dy[5] = {1,0,-1,0,1};
for (int k=0;k<4;k++){
int u[2];
for (int d=0;d<2;d++){
int px = x + dx[k+d];
int py = y + dy[k+d];
if (px < 0 || px >= H || py < 0 || py >= W) u[d] = N;
else u[d] = A[px*W+py];
}
int s = N, e = 0;
if (i < u[0] && i < u[1]){
s = i + Z;
e = min(u[0],u[1]) + Z;
}
if (u[0] < i && u[1] < i){
s = max(u[0],u[1]) + Z;
e = i + Z;
}
if (s < e){
IT[s].add(+p);
IT[e].add(-p);
if (up){
ups.insert(s);
ups.insert(e);
}
}
}
}
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;
for (int i=0;i<N;i++) A[R[i]*W+C[i]] = i;
IT[N+Z].add(10000);
for (int i=0;i<N;i++) add(i,1,false);
for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] * IT[i*2+1];
}
int swap_seats(int a, int b)
{
int dx[5] = {0,1,0,-1,0};
int dy[5] = {1,0,-1,0,0};
for (int i : {a,b}) for (int k=0;k<5;k++){
int x = R[i] + dx[k];
int y = C[i] + dy[k];
if (x < 0 || x >= H || y < 0 || y >= W) continue;
add(A[x*W+y],-1);
}
swap(R[a],R[b]);
swap(C[a],C[b]);
A[R[a]*W+C[a]] = a;
A[R[b]*W+C[b]] = b;
for (int i : {a,b}) for (int k=0;k<5;k++){
int x = R[i] + dx[k];
int y = C[i] + dy[k];
if (x < 0 || x >= H || y < 0 || y >= W) continue;
add(A[x*W+y],+1);
}
for (int x : ups) upd(x);
ups.clear();
return IT[1].min == 4 ? IT[1].cnt : 0;
}
