#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }
const ll INF = 1e18;
struct SegTree {
struct Node {
ll mn, cnt;
Node ( ) { }
Node (ll mn, ll cnt): mn(mn), cnt(cnt) { }
Node operator +(const Node &o) {
return {
min(mn, o.mn),
(mn <= o.mn ? cnt : 0) +
(o.mn <= mn ? o.cnt : 0)
};
};
};
Node IDEM = {0, 1};
vector<Node> st;
vll lz;
ll n;
SegTree () { }
SegTree (ll n): st(4*n+4, IDEM), lz(4*n+4,0), n(n) { }
void push (ll id, ll l, ll r) {
st[id].mn += lz[id];
if (l != r) {
lz[id*2] += lz[id];
lz[id*2+1] += lz[id];
}
lz[id] = 0;
}
void update (ll l, ll r, ll c) { update(1, 0, n-1, l, r, c); }
void update (ll id, ll l, ll r, ll i, ll j, ll c) {
push(id, l, r);
if (r < i || j < l) return;
if (i <= l && r <= j) {
lz[id] += c;
push(id, l, r);
return;
}
ll m = (l+r)/2;
update(id*2, l, m, i, j, c);
update(id*2+1, m+1, r, i, j, c);
st[id] = st[id*2] + st[id*2+1];
}
};
const int N = 1e6 + 7;
ll a[N], h, w, pos[N];
SegTree st;
void upd (ll i, ll j, ll c) {
if (j < i) swap(i, j);
ll A = (i == -1 ? w : a[i]), B = (j == w ? w : a[j]);
if (A > B) swap(A, B);
st.update(A, B-1, +c);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
st = SegTree(W);
fo (i, W) a[C[i]] = i;
fo (i, W) pos[i] = C[i];
fo (i, W+1) {
upd (i-1, i, +1);
}
}
int swap_seats(int x, int y) {
ll i = pos[x], j = pos[y];
upd(i-1, i, -1);
upd(i, i+1, -1);
if (j != i+1) upd(j-1, j, -1);
if (j+1 != i) upd(j, j+1, -1);
swap(a[i], a[j]);
swap(pos[x], pos[y]);
upd(i-1, i, +1);
upd(i, i+1, +1);
if (j != i+1) upd(j-1, j, +1);
if (j+1 != i) upd(j, j+1, +1);
auto ans = st.st[1];
return (ans.mn == 2 ? ans.cnt : 0);
}
