// #pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int points[MAXN];
int inv[MAXN];
bool active[MAXN];
int n;
typedef pair<int, int> pii;
pii comb(pii &a, pii &b) {
if (a.first != b.first) return min(a, b);
return pii(a.first, a.second+b.second);
}
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
pii mn = pii(0, 1);
int lz = 0;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
mn = comb(l->mn, r->mn);
}
}
void set_lz(int v) {
lz += v;
mn.first += v;
}
void prop() {
if (lz == 0) return;
assert(l);
l->set_lz(lz);
r->set_lz(lz);
lz = 0;
}
void upd(int lv, int rv, int v) {
if (lp > rv || rp < lv) return;
if (lp >= lv && rp <= rv) {
return set_lz(v);
}
prop();
l->upd(lv, rv, v);
r->upd(lv, rv, v);
mn = comb(l->mn, r->mn);
}
};
stree *tree;
void make(int i, bool unmake) {
if (active[i] != unmake) return;
active[i] ^= 1;
int mult = (unmake) ? -1 : 1;
bool lcomp = (i == 0) ? 1 : points[i-1] > points[i];
bool rcomp = (i == n-1) ? 1 : points[i+1] > points[i];
if (lcomp && rcomp) tree->upd(0, points[i]-1, -mult);
if (!lcomp && !rcomp) tree->upd(0, points[i]-1, mult);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = W;
assert(H == 1);
for (int i = 0; i < n; i++) {
points[C[i]] = i;
inv[i] = C[i];
assert(R[i] == 0);
}
tree = new stree(0, n-1);
for (int i = 0; i < n; i++) make(i, 0);
}
int swap_seats(int a, int b) {
a = inv[a]; b = inv[b];
for (int i = max(0, a-1); i <= min(n-1, a+1); i++) make(i, 1);
for (int i = max(0, b-1); i <= min(n-1, b+1); i++) make(i, 1);
swap(inv[points[a]], inv[points[b]]);
swap(points[a], points[b]);
for (int i = max(0, a-1); i <= min(n-1, a+1); i++) make(i, 0);
for (int i = max(0, b-1); i <= min(n-1, b+1); i++) make(i, 0);
assert(tree->mn.first == 0);
assert(tree->mn.second >= 2);
return tree->mn.second;
}
