#include <bits/stdc++.h>
#include "seats.h"
//#include "grader.cpp"
using namespace std;
const int N = (int)1e6 + 7;
vector <int> vec;
int n;
struct T {
pair <int, int> tree[N * 4];
int add[N * 4];
T() {
}
void push(int v, int l, int r) {
if (add[v] == 0) return ;
if (l != r) {
add[v + v] += add[v];
add[v + v + 1] += add[v];
}
tree[v].first += add[v];
add[v] = 0;
}
pair <int, int> gather(pair <int, int> l, pair <int, int> r) {
pair <int, int> res;
if (l.first == r.first) {
res = l;
res.second += r.second;
} else if (l.first < r.first) {
res = l;
} else {
res = r;
}
return res;
}
void build(int v = 1, int l = 0, int r = n - 1) {
if (l == r) {
tree[v] = {0, 1};
add[v] = 0;
return ;
}
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
tree[v] = gather(tree[v + v], tree[v + v + 1]);
}
void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1) {
push(v, tl, tr);
if (tl > r || tr < l) return ;
if (l <= tl && tr <= r) {
add[v] += val;
push(v, tl, tr);
return ;
}
int mid = (tl + tr) >> 1;
upd(l, r, val, v + v, tl, mid);
upd(l, r, val, v + v + 1, mid + 1, tr);
tree[v] = gather(tree[v + v], tree[v + v + 1]);
//cout << v << ' ' << tl << ' ' << tr << ' ' << tree[v].first << ' ' << tree[v].second << endl;
}
pair <int, int> get(int l, int r, int v = 1, int tl = 0, int tr = n - 1) {
push(v, tl, tr);
if (tl > r || tr < l) return {1e9, 0};
if (l <= tl && tr <= r) return tree[v];
int mid = (tl + tr) >> 1;
return gather(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}
};
T tr;
vector <int> r, c;
int getval(int x) {
int val = 0;
val += (c[x] == 0 || vec[c[x] - 1] > x);
val += (c[x] == n - 1 || vec[c[x] + 1] > x);
return val;
}
void add(int x) {
int val = getval(x);
if (val == 2) {
tr.upd(x, n - 1, 2);
} else if (val == 0) {
tr.upd(x, n - 1, -2);
}
}
void del(int x) {
int val = getval(x);
if (val == 2) {
tr.upd(x, n - 1, -2);
} else if (val == 0) {
tr.upd(x, n - 1, 2);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
r = R;
c = C;
n = H * W;
tr.build();
vec.resize(n);
for (int i = 0; i < n; i++) {
vec[C[i]] = i;
}
for (int i = 0; i < n; i++) {
add(i);
}
//for (int to : vec) {
//cout << to << ' ';
//}
//cout << endl;
//for (int i = 0; i < n; i++) {
//cout << tr.get(i, i).first << ' ';
//}
//cout << endl;
//cout << tr.get(0, n - 1).second << endl;
}
int used[N];
void rollback(int x) {
if (!used[x]) {
del(x);
used[x] = 1;
}
if (c[x] > 0 && !used[vec[c[x] - 1]]) {
used[vec[c[x] - 1]] = 1;
del(vec[c[x] - 1]);
}
if (c[x] + 1 < n && !used[vec[c[x] + 1]]) {
used[vec[c[x] + 1]] = 1;
del(vec[c[x] + 1]);
}
}
void add1(int x) {
if (used[x] == 1) {
add(x);
used[x] = 0;
}
if (c[x] > 0 && used[vec[c[x] - 1]]) {
add(vec[c[x] - 1]);
used[vec[c[x] - 1]] = 0;
}
if (c[x] + 1 < n && used[vec[c[x] + 1]]) {
add(vec[c[x] + 1]);
used[vec[c[x] + 1]] = 0;
}
}
int swap_seats(int a, int b) {
rollback(a);
rollback(b);
swap(c[a], c[b]);
vec[c[a]] = a; vec[c[b]] = b;
add1(a);
add1(b);
//for (int i = 0; i < n; i++) {
//cout << tr.get(i, i).first << ' ';
//}
//cout << endl;
return tr.get(0, n - 1).second;
}
