#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
const int MAXN=1e6+10;
typedef tuple<int,int,int> trio;
typedef pair<int,int> pii;
struct node{
int mn,freq;
node operator+(const node&nd){
node c;
c.mn=min(this->mn,nd.mn);
c.freq=0;
if(c.mn==this->mn) c.freq+=this->freq;
if(c.mn==nd.mn)c.freq+=nd.freq;
return c;
};
};
int n,lz[4*MAXN];
vector<int> v;
node seg[4*MAXN];
void unlz(int ind,int l,int r){
seg[ind].mn+=lz[ind];
if(l!=r){
lz[2*ind]+=lz[ind];
lz[2*ind+1]+=lz[ind];
}
lz[ind]=0;
}
void build(int ind=1,int l=0,int r=n-1){
seg[ind].freq=r-l+1;
if(l==r)return;
int m=(l+r)>>1;
build(2*ind,l,m); build(2*ind+1,m+1,r);
}
void updt(int ind,int l,int r,int a,int b,int val){
unlz(ind,l,r);
if(a>r || l>b)return;
if(a<=l && b>=r){
lz[ind]+=val;
unlz(ind,l,r);
return;
}
int m=(l+r)>>1;
updt(2*ind,l,m,a,b,val); updt(2*ind+1,m+1,r,a,b,val);
seg[ind]=seg[2*ind]+seg[2*ind+1];
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
v.resize(W*H);
fall(i,0,W*H-1) v[i]=C[i];
n=H*W;
build();
updt(1,0,n-1,v[0],n-1,1); updt(1,0,n-1,v.back(),n-1,1);
fall(i,1,n-1){
updt(1,0,n-1,min(v[i],v[i-1]),max(v[i],v[i-1])-1,1);
}
return;
}
int swap_seats(int a, int b){
if(a>b) swap(a,b);
if(a) updt(1,0,n-1,min(v[a],v[a-1]),max(v[a],v[a-1])-1,-1);
else updt(1,0,n-1,v[a],n-1,-1);
if(b!=n-1) updt(1,0,n-1,min(v[b],v[b+1]),max(v[b],v[b+1])-1,-1);
else updt(1,0,n-1,v[b],n-1,-1);
updt(1,0,n-1,min(v[b],v[b-1]),max(v[b],v[b-1])-1,-1);
if(a+1!=b) updt(1,0,n-1,min(v[a],v[a+1]),max(v[a],v[a+1])-1,-1);
swap(v[a],v[b]);
if(a) updt(1,0,n-1,min(v[a],v[a-1]),max(v[a],v[a-1])-1,1);
else updt(1,0,n-1,v[a],n-1,1);
if(b!=n-1) updt(1,0,n-1,min(v[b],v[b+1]),max(v[b],v[b+1])-1,1);
else updt(1,0,n-1,v[b],n-1,1);
updt(1,0,n-1,min(v[b],v[b-1]),max(v[b],v[b-1])-1,1);
if(a+1!=b) updt(1,0,n-1,min(v[a],v[a+1]),max(v[a],v[a+1])-1,1);
return seg[1].freq;
}
