#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class Segtree {
private:
struct Node {
int mn, c;
};
int n; vector<Node> seg; vector<int> lazy;
Node merge(Node &a, Node &b) {
if (a.mn < b.mn) return a;
if (a.mn > b.mn) return b;
return Node({a.mn, a.c + b.c});
}
public:
Segtree() {}
Segtree(int n) {
seg.resize(4 * n); lazy.resize(4 * n);
this->n = n;
build(1, 0, n - 1);
}
void build(int i, int l, int r) {
lazy[i] = 0;
if (l == r) {
seg[i] = {0, 1};
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void push(int i, int l, int r) {
if (!lazy[i]) return;
seg[i].mn += lazy[i];
if (l != r) {
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
}
lazy[i] = 0;
}
void upd(int i, int l, int r, int ql, int qr, int qv) {
push(i, l, r);
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
lazy[i] += qv;
push(i, l, r);
return;
}
int mid = (l + r) / 2;
upd(i * 2, l, mid, ql, qr, qv);
upd(i * 2 + 1, mid + 1, r, ql, qr, qv);
seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
}
void update(int ql, int qr, int qv) {
upd(1, 0, n - 1, ql, qr, qv);
}
int query() {
assert(seg[1].mn == 2);
return seg[1].c;
}
};
int w;
int arr[1000005], pos[1000005];
Segtree st;
void cont(int i, int j, int d) {
if (i > j) swap(i, j);
if (i == -1) {
st.update(arr[j], w - 1, d);
} else if (j == w) {
st.update(arr[i], w - 1, d);
} else {
int x = min(arr[i], arr[j]), y = max(arr[i], arr[j]);
st.update(x, y - 1, d);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
assert(H == 1); w = W; st = Segtree(W);
for (int i = 0; i < W; i++) {
arr[C[i]] = i;
pos[i] = C[i];
}
for (int i = 0; i <= W; i++) cont(i - 1, i, 1);
}
int swap_seats(int a, int b) {
int l = pos[a], r = pos[b];
cont(l, l - 1, -1); cont(l, l + 1, -1);
cont(r, r - 1, -1); cont(r, r + 1, -1);
swap(arr[l], arr[r]);
swap(pos[a], pos[b]);
cont(l, l - 1, 1); cont(l, l + 1, 1);
cont(r, r - 1, 1); cont(r, r + 1, 1);
return st.query();
}
