#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
template <class F, class S>
bool chmin(F &u, const S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class S>
bool chmax(F &u, const S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int inf = 1e9;
const int N = 1e6 + 1;
vector <int> R, C, p;
int h, w;
struct SegTree{
struct Info{
int mn, cnt, s;
Info(int mn = inf, int cnt = 1, int s = inf) : mn(mn), cnt(cnt), s(s) {}
};
Info T[N * 4];
void merge(Info &rt, const Info &lf, const Info &rg){
rt = Info();
rt.mn = min(lf.mn, rg.mn + lf.cnt);
rt.cnt = (lf.mn == rt.mn) * lf.cnt + (rt.mn == rg.mn) * rg.cnt;
rt.s = lf.s + rg.s;
}
void upd(int v, int l, int r, int p, int x){
if ( l == r ){
T[v] = Info(x, 1, x);
return;
}
int m = (l + r) / 2;
if ( p <= m ) upd(v * 2, l, m, p, x);
else upd(v * 2 + 1, m + 1, r, p, x);
merge(T[v], T[v * 2], T[v * 2 + 1]);
}
void upd(int p, int x){
if ( x == -3 ) return;
upd(1, 0, N - 1, p, x);
}
int qry(){ return T[1].cnt; }
} seg;
int f(int u){
if ( u < 0 || u >= w ) return -3;
int cnt = !u * -2, x = C[u];
cnt += (x == 0 || p[x - 1] > u) ? 1 : -1;
cnt += (x == w - 1 || p[x + 1] > u) ? 1 : -1;
return cnt;
}
void give_initial_chart(int H, int W, std::vector<int> R_, std::vector<int> C_) {
h = H, w = W, R = R_, C = C_;
p.resize(w);
for ( int i = 0; i < w; i++ ){
p[C[i]] = i;
}
for ( int i = 0; i < w; i++ ){
seg.upd(i, f(i));
}
}
int swap_seats(int a, int b) {
swap(C[a], C[b]);
swap(p[C[a]], p[C[b]]);
for ( auto i: {-1, 0, 1} ){
seg.upd(a, f(a + i));
seg.upd(b, f(b + i));
}
return seg.qry();
}
