#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"
constexpr i32 INF = 1001001001;
i32 ceil_log2(i32 n) {
i32 l = 0;
while ((1 << l) < n) {
++l;
}
return l;
}
class RangeAddCountMin {
using Value = pair<i32, i32>;
using Func = i32;
static Value id() { return Value(INF, 0); }
static Value op(Value x, Value y) {
i32 mn = min(x.first, y.first);
i32 cnt = 0;
if (x.first == mn) {
cnt += x.second;
}
if (y.first == mn) {
cnt += y.second;
}
return Value(mn, cnt);
}
static Func func_id() { return 0; }
static Func composite(Func f, Func g) { return f + g; }
static Value apply(Func f, Value x) { return Value(f + x.first, x.second); }
i32 lg, n;
V<Value> val;
V<Func> fun;
void push(i32 idx) {
if (idx < n) {
REP(i, 2) {
val[2 * idx + i] = apply(fun[idx], val[2 * idx + i]);
fun[2 * idx + i] = composite(fun[idx], fun[2 * idx + i]);
}
fun[idx] = func_id();
}
}
void push_(i32 idx) {
PER(i, 1, lg + 1) { push(idx >> i); }
}
void apply_(i32 idx, Func f) {
val[idx] = apply(f, val[idx]);
fun[idx] = composite(f, fun[idx]);
}
void update(i32 idx) {
if (idx < n) {
val[idx] = op(val[2 * idx], val[2 * idx + 1]);
}
}
public:
RangeAddCountMin() = default;
RangeAddCountMin(i32 _n)
: lg(ceil_log2(_n)),
n(1 << lg),
val(2 * n, id()),
fun(2 * n, func_id()) {
REP(i, n, 2 * n) {
val[i] = Value(0, 1);
}
PER(i, 1, n) {
val[i] = op(val[2 * i], val[2 * i + 1]);
}
}
void range_add(i32 l, i32 r, i32 v) {
if (l == r) {
return;
}
//cout << l << ' ' << r << ' ' << v << '\n';
l += n;
r += n;
push_(l);
push_(r - 1);
i32 l_ = l;
i32 r_ = r;
while (l < r) {
if (l & 1) {
apply_(l++, v);
}
if (r & 1) {
apply_(--r, v);
}
l /= 2;
r /= 2;
}
REP(i, lg + 1) {
if ((l_ >> i << i) != l_) {
update(l_ >> i);
}
if ((r_ >> i << i) != r_) {
update(r_ >> i);
}
}
/*REP(i, 1, 2 * n) {
cout << "(" << val[i].first << ", " << val[i].second << ")" << " \n"[i + 1 == 2 * n];
}
REP(i, 1, 2 * n) {
cout << fun[i] << " \n"[i + 1 == 2 * n];
}*/
}
pair<i32, i32> get_min_and_cnt(i32 l, i32 r) {
if (l == r) {
return id();
}
l += n;
r += n;
push_(l);
push_(r - 1);
Value ret = id();
while (l < r) {
if (l & 1) {
ret = op(ret, val[l++]);
}
if (r & 1) {
ret = op(ret, val[--r]);
}
l /= 2;
r /= 2;
}
return ret;
}
};
i32 h, w;
V<i32> r, c;
V<i32> pos;
V<i32> ord;
RangeAddCountMin ds;
void process(i32 i, i32 wt) {
if (i == -1) {
ds.range_add(ord[0], w, wt);
} else if (i == w - 1) {
ds.range_add(ord[w - 1], w, wt);
} else {
i32 x = ord[i], y = ord[i + 1];
if (x > y) {
swap(x, y);
}
ds.range_add(x, y, wt);
}
}
void give_initial_chart(i32 _h, i32 _w, V<i32> _r, V<i32> _c) {
h = _h;
w = _w;
r = _r;
c = _c;
assert(h == 1);
pos = c;
ord.resize(w);
REP(i, w) { ord[pos[i]] = i; }
ds = RangeAddCountMin(w);
REP(i, -1, w) {
process(i, 1);
}
}
i32 swap_seats(i32 a, i32 b) {
if (pos[a] > pos[b]) {
swap(a, b);
}
bool adj = pos[b] == pos[a] + 1;
process(pos[a] - 1, -1);
process(pos[a], -1);
if (!adj) process(pos[b] - 1, -1);
process(pos[b], -1);
swap(ord[pos[a]], ord[pos[b]]);
swap(pos[a], pos[b]);
process(pos[b] - 1, 1);
process(pos[b], 1);
if (!adj) process(pos[a] - 1, 1);
process(pos[a], 1);
auto ret = ds.get_min_and_cnt(0, w);
return ret.second;
}
