#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct segtree{
struct DDT{
int mn,mnc,lz,l,r;
DDT(){mnc=1,mn=lz=0;}
DDT(DDT a,DDT b){
*this=a;
if(b.mn<mn)
mn=b.mn,mnc=0;
if(b.mn==mn)
mnc+=b.mnc;
}
} T[1<<21];
void pd(int i){
int k=T[i].lz;
if(k){T[i].lz=0,
T[i].mn+=k;
if(i<1<<20)
T[i*2].lz+=k,
T[i*2+1].lz+=k;
}
}
void upd(int i,int l,int r,int ll,int rr,int v){
pd(i);if(ll<=l&&r<=rr)
return T[i].lz=v,pd(i);
if(ll>r||l>rr) return;
upd(i*2,l,l+r>>1,ll,rr,v);
upd(i*2+1,l+r+2>>1,r,ll,rr,v);
T[i]=DDT(T[i*2],T[i*2+1]);
T[i].l=l,T[i].r=r;
}
} ST;
vector<int>C_;
int app[1000100];
bitset<1000100>had;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for(auto&i:C)i++;
C.insert(C.begin(),0);
C_=C;
int ranges=0;
memset(app,1,sizeof app);
for(int i=1;i<=H*W;i++){
ranges++;
app[C[i]]=i;
had[C[i]]=1;
ranges-=had[C[i]-1];
ranges-=had[C[i]+1];
ST.upd(1,1,H*W,i,i,ranges);
}
}
inline void do_contrib(int l,int r,int coef){
int v=C_[l];
int a=app[v-1],b=app[v+1];
ST.upd(1,1,C_.size()-1,l,r,coef);
ST.upd(1,1,C_.size()-1,max(a,l),r,-coef);
ST.upd(1,1,C_.size()-1,max(b,l),r,-coef);
}
int swap_seats(int a, int b) {
a++;b++; if(a>b)swap(a,b);
do_contrib(a,b-1,-1);
swap(C_[a],C_[b]);
app[C_[a]]=a;
app[C_[b]]=b;
do_contrib(a,b-1,1);
return ST.T[1].mnc;
}
