#include "seats.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long int lld;
int h,w;
int per[1000010];
int inv[1000010];
int arr[1000010];
//segtree
int sum[8000000];
int minimo[8000000];
int counter[8000000];
int cnt;
void update_pos(int i){
int pos=inv[i];
arr[i]=-1;
if(pos==0 || per[pos-1]>i){
arr[i]++;
}
if(pos==w-1 || per[pos+1]>i){
arr[i]++;
}
}
void build(int a, int b, int node){
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
sum[node]=sum[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==minimo[2*node+1]+sum[2*node]){
counter[node]+=counter[2*node+1];
}
}
void update(int a, int b, int node, int pos){
if(pos<a || b<pos)return;
if(a==b){
sum[node]=arr[a];
minimo[node]=arr[a];
counter[node]=1;
return;
}
int mid=(a+b)/2;
update(a,mid,2*node,pos);
update(mid+1,b,2*node+1,pos);
sum[node]=sum[2*node]+sum[2*node+1];
minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
counter[node]=0;
if(minimo[node]==minimo[2*node]){
counter[node]+=counter[2*node];
}
if(minimo[node]==minimo[2*node+1]+sum[2*node]){
counter[node]+=counter[2*node+1];
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {cnt=0;
h=H;
w=W;
for(int i=0;i<w;i++){
inv[i]=C[i];
per[C[i]]=i;
}
for(int i=0;i<w;i++){
int pos=inv[i];
arr[i]=-1;
if(pos==0 || per[pos-1]>i){
arr[i]++;
}
if(pos==w-1 || per[pos+1]>i){
arr[i]++;
}
//cout<<arr[i]<<endl;
}
build(0,w-1,1);
//cout<<counter[1]<<endl;
/*for(int i=1;i<8;i++){
cout<<counter[i]<<" "<<i<<endl;
}*/
}
int swap_seats(int a, int b) {
/*cnt++;
if(cnt>100){
for(int i=0;i<1;i+=0){
}
}*/
int pos_a=inv[a];
int pos_b=inv[b];
swap(inv[a],inv[b]);
swap(per[pos_a],per[pos_b]);
update_pos(a);
update(0,w-1,1,a);
update_pos(b);
update(0,w-1,1,b);
if(inv[a]>0){
update_pos(per[inv[a]-1]);
update(0,w-1,1,per[inv[a]-1]);
}
if(inv[a]<w-1){
update_pos(per[inv[a]+1]);
update(0,w-1,1,per[inv[a]+1]);
}
if(inv[b]>0){
update_pos(per[inv[b]-1]);
update(0,w-1,1,per[inv[b]-1]);
}
if(inv[b]<w-1){
update_pos(per[inv[b]+1]);
update(0,w-1,1,per[inv[b]+1]);
}
/*for(int i=1;i<8;i++){
cout<<counter[i]<<" "<<i<<endl;
}*/
//for(int i=0;i<w;i++)cout<<arr[i]<<endl;
return counter[1];
}
