#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll LINF=(1LL<<62)-(1LL<<31);
#include "seats.h"
struct SegTree{
using T=array<ll,3>;
//{cum,min,cnt}
T op(T x,T y){
T ret;
ret[0]=x[0]+y[0];
ret[1]=min(x[0]+y[1],x[1]);
ret[2]=0;
if(ret[1]==x[1]){
ret[2]+=x[2];
}
if(ret[1]==x[0]+y[1]){
ret[2]+=y[2];
}
return ret;
}
T e(){
return {0,1<<30,0};
}
vector<T> val;
int size;
SegTree(int sz){
size=sz;
val.resize(size*2,e());
}
void set(int pos,T v){
pos+=size;
val[pos]=v;
while(pos>1){
pos/=2;
val[pos]=op(val[pos*2],val[pos*2+1]);
}
}
T prod(int lf,int ri){
lf+=size;
ri+=size;
T ret_lf=e();
T ret_ri=e();
while(lf<ri){
if(lf&1){
ret_lf=op(ret_lf,val[lf]);
lf++;
}
if(ri&1){
ri--;
ret_ri=op(val[ri],ret_ri);
}
lf/=2;
ri/=2;
}
return op(ret_lf,ret_ri);
}
};
//c...pos now...seats
vector<int> c;
vector<int> now;
vector<int> cum;
int w;
SegTree seg(0);
void seg_set(int pos){
seg.set(pos,array<ll,3>{cum[pos],cum[pos],1});
}
void add(int pos,int val){
if(pos!=0){
if(now[pos-1]<now[pos]){
cum[now[pos-1]]+=val;
cum[now[pos]]-=val;
seg_set(now[pos-1]);
}
}
if(pos!=w+1){
if(now[pos+1]<now[pos]){
cum[now[pos+1]]+=val;
cum[now[pos]]-=val;
seg_set(now[pos+1]);
}
}
seg_set(now[pos]);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
c = C;
w = W;
rep(i,W){
c[i]++;
}
c.emplace_back(0);
c.emplace_back(W+1);
now.resize(W+2);
cum.resize(W+2,0);
seg=SegTree(W+2);
rep(i,W+2){
seg.set(i,array<ll,3>{0,0,1});
}
rep(i,W+2){
now[c[i]]=i;
}
rep(i,W+2){
add(i,1);
}
}
int swap_seats(int a, int b) {
vector<int> fix={c[a],c[a]+1,c[a]-1,c[b],c[b]+1,c[b]-1};
sort(all(fix));
fix.erase(unique(all(fix)),fix.end());
for(int i:fix){
add(i,-1);
}
swap(c[a],c[b]);
swap(now[c[a]],now[c[b]]);
for(int i:fix){
add(i,1);
}
return seg.prod(0,w)[2];
}
