#include<bits/stdc++.h>
using namespace std;
const int siz = 1e6+2;
int p[siz];
int v[siz];
int N;
struct node{
int l,r,mid,maxi,cam,pl; // num of elements equal to maxi
node* sl = NULL,*sr;
node(int li, int ri){
l = li, r = ri, mid = (l+r)/2, maxi = 0,cam=0,pl=0;
if(l<r){
sl = new node(l,mid);
sr = new node(mid+1,r);
}else if(l > 0 && l <= N)cam = 1;
}
void push(){
if(sl == NULL)return;
sl->maxi+=pl;
sr->maxi+=pl;
sr->pl+=pl;
sl->pl+=pl;
pl=0;
}
void update(int a, int b, int val){
if(a > r || b < l)return;
push();
if(a <= l && b>=r){
maxi+=val;
pl += val;
}else{
sl->update(a,b,val);
sr->update(a,b,val);
if(sl->maxi > sr->maxi)cam = sl->cam;
else if(sl->maxi < sr->maxi)cam = sr->cam;
else cam = sl->cam+sr->cam;
maxi = max(sl->maxi,sr->maxi);
}
}
};
node* seg;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
N=W;
p[0]=N+1;
p[N+1]=N+1;
seg = new node(1,N);
for(int i = 0; i <W; i++)p[C[i]+1]=i+1;
for(int i = 0; i < N; i++)v[i+1] = C[i]+1;
for(int i = 1; i < N; i++){
seg->update(max(p[i],p[i+1]),N,1);
}
for(int i = 1; i <= N; i++)seg->update(i,N,-1);
}
int swap_seats(int a, int b) {
a++,b++;
seg->update(max(p[v[a]],p[v[a]+1]),1e6,-1);
seg->update(max(p[v[a]],p[v[a]-1]),1e6,-1);
seg->update(max(p[v[b]],p[v[b]+1]),1e6,-1);
seg->update(max(p[v[b]],p[v[b]-1]),1e6,-1);
swap(p[v[a]],p[v[b]]);
seg->update(max(p[v[a]],p[v[a]+1]),1e6,1);
seg->update(max(p[v[a]],p[v[a]-1]),1e6,1);
seg->update(max(p[v[b]],p[v[b]+1]),1e6,1);
seg->update(max(p[v[b]],p[v[b]-1]),1e6,1);
swap(v[a],v[b]);
return seg->cam;
}
