#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
vi a,arr,X;
int n;
vector<ti> st;
//cnt,min,sum
void build(int x,int l,int r){
if(l==r){
st[x]={1,a[l],a[l]};
return;
}
int m=(l+r)/2;
build(2*x,l,m);
build(2*x+1,m+1,r);
auto [p1,q1,r1]=st[2*x];
auto [p2,q2,r2]=st[2*x+1];
q2+=r1;
if(q1==q2)st[x]={p1+p2,q1,r1+r2};
else if(q1<q2)st[x]={p1,q1,r1+r2};
else st[x]={p2,q2,r1+r2};
}
void update(int x,int l,int r,int p,int v){
if(l==r){
st[x]={1,v,v};
return;
}
int m=(l+r)/2;
if(m>=p)update(2*x,l,m,p,v);
else update(2*x+1,m+1,r,p,v);
auto [p1,q1,r1]=st[2*x];
auto [p2,q2,r2]=st[2*x+1];
q2+=r1;
if(q1==q2)st[x]={p1+p2,q1,r1+r2};
else if(q1<q2)st[x]={p1,q1,r1+r2};
else st[x]={p2,q2,r1+r2};
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=W;
X=C;
a.resize(n,0);arr.resize(n);
REP(i,0,n)arr[X[i]]=i;
REP(i,0,n){
if(X[i]-1<0||arr[X[i]-1]>arr[X[i]])a[i]++;
else a[i]--;
if(X[i]+1>=n||arr[X[i]+1]>arr[X[i]])a[i]++;
else a[i]--;
}
st.resize(4*n+1);
build(1,0,n-1);
}
int swap_seats(int x, int y) {
swap(arr[X[x]],arr[X[y]]);
swap(X[x],X[y]);
x=X[x];y=X[y];
for(int i=max(0,x-1);i<=min(n-1,x+1);i++){
a[arr[i]]=0;
if(i-1<0||arr[i-1]>=arr[i])a[arr[i]]++;
else a[arr[i]]--;
if(i+1>=n||arr[i+1]>=arr[i])a[arr[i]]++;
else a[arr[i]]--;
update(1,0,n-1,arr[i],a[arr[i]]);
}
for(int i=max(0,y-1);i<=min(n-1,y+1);i++){
a[arr[i]]=0;
if(i-1<0||arr[i-1]>=arr[i])a[arr[i]]++;
else a[arr[i]]--;
if(i+1>=n||arr[i+1]>=arr[i])a[arr[i]]++;
else a[arr[i]]--;
update(1,0,n-1,arr[i],a[arr[i]]);
}
if(get<1>(st[1])==2)return get<0>(st[1]);
return 0;
}
