#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
struct Node{
int minVal, cntMin;
Node(int x = 0, int cnt = 1){
minVal = x;
cntMin = cnt;
}
void update(int x){
minVal += x;
}
Node operator + (const Node &oth){
if (minVal < oth.minVal)
return *this;
if (minVal > oth.minVal)
return oth;
return Node(minVal, cntMin + oth.cntMin);
}
};
struct SegmentTree{
int n;
vector<int> lazy;
vector<Node> d;
void build(int id, int l, int r){
lazy[id] = 0;
if (l == r){
d[id] = Node(0, 1);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
d[id] = d[id << 1] + d[id << 1 | 1];
}
void init(int _n){
n = _n;
d.assign(n * 4 + 1, Node(0, 1));
lazy.assign(n * 4 + 1, 0);
}
void doLazy(int id, int l, int r){
d[id].update(lazy[id]);
if (l < r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
doLazy(id, l, r);
if (v < l || r < u)
return;
if (u <= l && r <= v){
lazy[id] += val;
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
d[id] = d[id << 1] + d[id << 1 | 1];
}
void update(int pos, int val){
update(1, 0, n - 1, pos, n - 1, val);
}
int getCnt(){
doLazy(1, 0, n - 1);
assert(d[1].minVal == 2);
return d[1].cntMin;
}
} st;
int n;
vector<int> val, pos;
void updateLink(int l, int type){
int r = l + 1;
if (l < 0) {
st.update(val[r], type);
} else if (r >= n) {
st.update(val[l], type);
} else {
st.update(min(val[l], val[r]), type);
st.update(max(val[l], val[r]), -type);
}
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
assert(h == 1);
n = w;
val.resize(n);
pos.resize(n);
pos = c;
for(int i = 0; i < n; i++)
val[pos[i]] = i;
st.init(n);
for(int i = 0; i <= n; i++)
updateLink(i - 1, +1);
}
int swap_seats(int a, int b) {
updateLink(pos[a] - 1, -1);
updateLink(pos[a], -1);
updateLink(pos[b] - 1, -1);
updateLink(pos[b], -1);
assert(val[pos[a]] == a);
assert(val[pos[b]] == b);
swap(val[pos[a]], val[pos[b]]);
swap(pos[a], pos[b]);
updateLink(pos[a] - 1, +1);
updateLink(pos[a], +1);
updateLink(pos[b] - 1, +1);
updateLink(pos[b], +1);
// cerr << "val: ";
// for(int x : val)
// cerr << x << ' ';
// cerr << endl;
return st.getCnt();
}
