#include <bits/stdc++.h>
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)(x).size()
#define ALL(x) begin(x), end(x)
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#include "seats.h"
using Rect = tuple<i32, i32, i32, i32>;
i32 h, w;
V<i32> r, c;
V<Rect> rect;
i32 ans;
i32 get_size(const Rect &rect) {
auto [u, d, l, r] = rect;
return (d - u) * (r - l);
}
Rect add_point(const Rect &rect, i32 x, i32 y) {
auto [u, d, l, r] = rect;
chmin(u, x);
chmax(d, x + 1);
chmin(l, y);
chmax(r, y + 1);
return Rect(u, d, l, r);
}
void give_initial_chart(i32 _h, i32 _w, V<i32> _r, V<i32> _c) {
h = _h;
w = _w;
r = _r;
c = _c;
rect.resize(h * w);
rect[0] = Rect(r[0], r[0] + 1, c[0], c[0] + 1);
REP(i, 1, h * w) {
rect[i] = add_point(rect[i - 1], r[i], c[i]);
}
ans = 1;
REP(i, h * w - 1) {
if (get_size(rect[i]) == i + 1) {
++ans;
}
}
}
i32 swap_seats(i32 a, i32 b) {
if (a > b) {
swap(a, b);
}
assert(b - a <= 10000);
REP(i, a, b) {
if (get_size(rect[i]) == i + 1) {
--ans;
}
}
swap(r[a], r[b]);
swap(c[a], c[b]);
REP(i, a, b) {
if (i == 0) {
rect[i] = Rect(r[i], r[i] + 1, c[i], c[i] + 1);
} else {
rect[i] = add_point(rect[i - 1], r[i], c[i]);
}
if (get_size(rect[i]) == i + 1) {
++ans;
}
}
return ans;
}
