#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define inf 1000000009
using namespace std;
typedef long long ll;
vector<vector<int> > mat;
int tmp[4];
int MX;
int H, W;
vector<int> R;
vector<int> C;
int lazy[4000006];
int minn[4000006];
int countt[4000006];
void stc(int node, int l, int r){
if (l == r){
minn[node] = 0;
countt[node] = 1;
lazy[node] = 0;
} else {
int m = (l+r)/2;
stc(node*2, l, m);
stc(node*2+1, m+1, r);
minn[node] = min(minn[node*2], minn[node*2+1]);
countt[node] = 0;
if (minn[node] == minn[node*2]) countt[node] += countt[node*2];
if (minn[node] == minn[node*2+1]) countt[node] += countt[node*2+1];
lazy[node] = 0;
}
}
int get(int node){
return minn[node] + lazy[node];
}
void push(int node){
minn[node] += lazy[node];
lazy[node*2+1] += lazy[node];
lazy[node*2] += lazy[node];
lazy[node] = 0;
}
void stu(int node, int l, int r, int sl, int sr, int val){
if (sl <= l && r <= sr){
lazy[node] += val;
} else if (r < sl ||sr < l){
return;
} else {
int m = (l+r)/2;
push(node);
stu(node*2, l, m, sl, sr, val);
stu(node*2+1, m+1, r, sl, sr, val);
minn[node] = min(get(node*2), get(node*2+1));
countt[node] = 0;
if (minn[node] == get(node*2)) countt[node] += countt[node*2];
if (minn[node] == get(node*2+1)) countt[node] += countt[node*2+1];
}
}
void yap(int i, int j){
tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
sort(tmp, tmp+4);
//cout << "yap: " << tmp[0] << ", " << tmp[1] << ", " << tmp[2] << ", " << tmp[3] << endl;
if (tmp[0] < tmp[1]) stu(1, 0, MX-1, tmp[0], tmp[1]-1, +1);
if (tmp[2] < tmp[3]) stu(1, 0, MX-1, tmp[2], tmp[3]-1, +1);
//if (tmp[0] < tmp[1]) cout << tmp[0] << " - " << tmp[1]-1 << ": +1" << endl;
//if (tmp[2] < tmp[3]) cout << tmp[2] << " - " << tmp[3]-1 << ": +1" << endl;
}
void boz(int i, int j){
tmp[0] = (i == -1 || j == -1) ? MX : mat[i][j];
tmp[1] = (i+1 == H || j == -1) ? MX : mat[i+1][j];
tmp[2] = (i == -1 || j+1 == W) ? MX : mat[i][j+1];
tmp[3] = (i+1 == H || j+1 == W) ? MX : mat[i+1][j+1];
sort(tmp, tmp+4);
if (tmp[0] != -1) stu(1, 0, MX-1, tmp[0], tmp[1]-1, -1);
if (tmp[2] != -1) stu(1, 0, MX-1, tmp[2], tmp[3]-1, -1);
}
int getnode(int node, int l, int r, int ind){
if (l == r) return get(node);
else {
int m = (l+r)/2;
push(node);
if (ind <= m) return getnode(node*2, l, m, ind);
else return getnode(node*2+1, m+1, r, ind);
}
}
void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {
H = HH;
W = WW;
R = RR;
C = CC;
MX = H*W;
mat.resize(H);
for (int i = 0; i < H; i++) mat[i].resize(W);
for (int i = 0; i < MX; i++){
mat[R[i]][C[i]] = i;
}
/*for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
cout << mat[i][j] << " ";
}
cout << endl;
}
cout << endl;*/
stc(1, 0, MX-1);
for (int i = -1; i < H; i++){
for (int j = -1; j < W; j++){
yap(i, j);
}
}
/*for (int i = 0; i < MX; i++) cout << getnode(1, 0, MX-1, i) << " ";
cout << endl;*/
}
int swap_seats(int a, int b) {
int i1 = R[a];
int j1 = C[a];
int i2 = R[b];
int j2 = C[b];
boz(i1-1, j1-1);
boz(i1-1, j1);
boz(i1, j1-1);
boz(i1, j1);
boz(i2-1, j2-1);
boz(i2-1, j2);
boz(i2, j2-1);
boz(i2, j2);
R[a] = i2;
R[b] = i1;
C[a] = j2;
C[b] = j1;
mat[i1][j1] = b;
mat[i2][j2] = a;
yap(i1, j1);
yap(i1, j1-1);
yap(i1-1, j1);
yap(i1-1, j1-1);
yap(i2, j2);
yap(i2, j2-1);
yap(i2-1, j2);
yap(i2-1, j2-1);
return countt[1];
}
/*
int main(){
freopen("stl.gir", "r", stdin);
int h, w;
cin >> h >> w;
vector<int> r;
vector<int> c;
for (int i = 0; i < h*w; i++){
int a, b;
cin >> a >> b;
r.pb(a);
c.pb(b);
}
give_initial_chart(h, w, r, c);
int q;
cin >> q;
while(q--){
int a, b;
cin >> a >> b;
cout << swap_seats(a, b) << endl;
}
}*/
