#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define vi vector<int>
#define vpii vector<pii>
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define defN 1000001
vector<pii>sg;
vector<int>lazy,grid,cols;
vector<int>nummys1,nummys2;
int n;
void init(int s, int e, int cn)
{
if(s==e)
{
sg[cn]=mp(nummys1[s],1);
return;
}
int m=(s+e)/2;
init(s,m,cn<<1);
init(m+1,e,(cn<<1)|1);
if(sg[cn<<1].ff==sg[(cn<<1)|1].ff){sg[cn]=mp(sg[cn<<1].ff,sg[cn<<1].ss+sg[(cn<<1)|1].ss);}
else {sg[cn]=min(sg[cn<<1],sg[(cn<<1)|1]);}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
cols=C;n=W;
sg=vector<pii>(4*n+1);
grid=vector<int>(n+2,n);
nummys1=vector<int>(n);
nummys2=vector<int>(n);
lazy=vector<int>(4*n+1,0);
int prev=0;
for(int i=0;i<n;i++){cols[i]++;}
for(int i=0;i<n;i++)
{
int cc=cols[i];
grid[cc]=i;int t1=2;
if(grid[cc-1]<i)t1-=2;
if(grid[cc+1]<i)t1-=2;
nummys2[i]=t1;
nummys1[i]=prev+t1;
prev=nummys1[i];
}
init(0,n-1,1);
}
void propagate(int s, int e, int cn)
{
sg[cn].ff+=lazy[cn];
if(s!=e)
{
lazy[cn<<1]=lazy[(cn<<1)|1]=lazy[cn];
}
lazy[cn]=0;
return;
}
void update(int s, int e, int cn, int reqs, int reqe, int val)
{
if(reqs<=s&&reqe>=e)
{
lazy[cn]+=val;
propagate(s,e,cn);
return;
}
int m=(s+e)/2;
if(reqs<=m){update(s,m,cn<<1,reqs,reqe,val);}
if(reqe>m){update(m+1,e,(cn<<1)|1,reqs,reqe,val);}
propagate(s,m,cn<<1);
propagate(m+1,e,(cn<<1)|1);
if(sg[cn<<1].ff==sg[(cn<<1)|1].ff){sg[cn]=mp(sg[cn<<1].ff,sg[cn<<1].ss+sg[(cn<<1)|1].ss);}
else sg[cn]=min(sg[cn<<1],sg[(cn<<1)|1]);
}
pii query()
{
propagate(0,n-1,1);
return sg[1];
}
void adj(int x)
{
int t2=nummys2[x];
int t1=2;
if(grid[cols[x]-1]<x){t1-=2;}
if(grid[cols[x]+1]<x){t1-=2;}
nummys2[x]=t1;
update(0,n-1,1,x,n-1,t1-t2);
}
int swap_seats(int a, int b)
{
int cc1=cols[a],cc2=cols[b];
swap(grid[cc1],grid[cc2]);
swap(cols[a],cols[b]);
adj(a);adj(b);
if(cc1!=n)adj(grid[cc1+1]);
if(cc1!=1)adj(grid[cc1-1]);
if(cc2!=n)adj(grid[cc2+1]);
if(cc2!=1)adj(grid[cc2-1]);
pii xx=query();
if(xx.ff!=2){return 0;}
else return xx.ss;
}
