#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>
using namespace std;
const int N = 11000;
int n, m;
vector<vector<int> > p;
int x[N], y[N];
long long tree[4 * N];
long long push[4 * N];
void Push(int V, int L, int R, int M)
{
tree[2 * V + 1] += (M - L) * push[V];
push[2 * V + 1] += push[V];
tree[2 * V + 2] += (R - M) * push[V];
push[2 * V + 2] += push[V];
push[V] = 0;
}
void add(int l, int r, long long val, int L = 0, int R = N, int V = 0)
{
if (r <= L || R <= l)
return;
if (l <= L && R <= r)
{
tree[V] += (R - L) * val;
push[V] += val;
return;
}
int M = (L + R) / 2;
Push(V, L, R, M);
add(l, r, val, L, M, 2 * V + 1);
add(l, r, val, M, R, 2 * V + 2);
}
long long get(int l, int r, int L = 0, int R = N, int V = 0)
{
if (r <= L || R <= l)
return 0;
if (l <= L && R <= r)
return tree[V];
int M = (L + R) / 2;
Push(V, L, R, M);
return
get(l, r, L, M, 2 * V + 1) +
get(l, r, M, R, 2 * V + 2);
}
void change_tile(int i, int j, int t)
{
int x[4] = {p[i][j], p[i + 1][j], p[i + 1][j + 1], p[i][j + 1]};
sort(x, x + 4);
add(x[0], x[1], t);
add(x[2], x[3], t * N);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c)
{
n = h + 2;
m = w + 2;
for (int i = 0; i < n; i++)
{
vector<int> e(m, 0);
p.push_back(e);
}
int t = h * w;
for (int i = 0; i < t; i++)
{
p[r[i] + 1][c[i] + 1] = i;
}
for (int i = 0; i < n - 1; i++)
{
p[i][0] = t;
t++;
}
for (int j = 0; j < m - 1; j++)
{
p[n - 1][j] = t;
t++;
}
for (int i = n - 1; i >= 1; i--)
{
p[i][m - 1] = t;
t++;
}
for (int j = m - 1; j >= 1; j--)
{
p[0][j] = t;
t++;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
x[p[i][j]] = i;
y[p[i][j]] = j;
}
}
for (int i = 0; i + 1 < n; i++)
{
for (int j = 0; j + 1 < m; j++)
{
change_tile(i, j, 1);
}
}
}
int get_cur()
{
int res = 0;
for (int i = 0; i < N; i++)
{
if (get(i, i + 1) == 4) res++;
}
return res;
}
int swap_seats(int a, int b)
{
int i1 = x[a], j1 = y[a];
int i2 = x[b], j2 = y[b];
change_tile(i1 - 1, j1 - 1, -1);
change_tile(i1 - 1, j1, -1);
change_tile(i1, j1 - 1, -1);
change_tile(i1, j1, -1);
change_tile(i2 - 1, j2 - 1, -1);
change_tile(i2 - 1, j2, -1);
change_tile(i2, j2 - 1, -1);
change_tile(i2, j2, -1);
swap(p[i1][j1], p[i2][j2]);
swap(x[a], x[b]);
swap(y[a], y[b]);
change_tile(i1 - 1, j1 - 1, 1);
change_tile(i1 - 1, j1, 1);
change_tile(i1, j1 - 1, 1);
change_tile(i1, j1, 1);
change_tile(i2 - 1, j2 - 1, 1);
change_tile(i2 - 1, j2, 1);
change_tile(i2, j2 - 1, 1);
change_tile(i2, j2, 1);
return get_cur();
}
/*int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<int> r(n * m), c(n * m);
for (int i = 0; i < n * m; i++)
{
cin >> r[i] >> c[i];
}
give_initial_chart(n, m, r, c);
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y;
cout << swap_seats(x, y) << "\n";
}
}*/
