#include "seats.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
struct segtree{
int Tmn[1<<21],Tmx[1<<21];
void upd(int i,int l,int r,int p,int x){
if(l==r)return void(Tmn[i]=Tmx[i]=x);
if(l+r>>1<p) upd(i*2+1,l+r+2>>1,r,p,x);
else upd(i*2,l,l+r>>1,p,x);
Tmn[i]=min(Tmn[i*2+1],Tmn[i*2]);
Tmx[i]=max(Tmx[i*2],Tmx[i*2+1]);
}
int querymx(int i,int l,int r,int rr){
if(r<=rr)return Tmx[i]; if(l>rr)return-1e9;
return max(querymx(i*2,l,l+r>>1,rr),
querymx(i*2+1,l+r+2>>1,r,rr));
}
int querymn(int i,int l,int r,int rr){
if(r<=rr)return Tmn[i]; if(l>rr)return 1e9;
return min(querymn(i*2,l,l+r>>1,rr),
querymn(i*2+1,l+r+2>>1,r,rr));
}
} STr,STc;
int span(int pos){
int ans=(STr.querymx(1,1,1e6,pos)-STr.querymn(1,1,1e6,pos)+1)*
(STc.querymx(1,1,1e6,pos)-STc.querymn(1,1,1e6,pos)+1);
return ans;
}
int ans;
vector<int>R_,C_;
void act(int i){
STr.upd(1,1,1e6,1+i,R_[i]),
STc.upd(1,1,1e6,1+i,C_[i]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
R_=R,C_=C;
for(int i=0;i<H*W;)
act(i++),ans+=i==span(i);
}
int qry(){
int ans=0;
int k=1,sz=R_.size();
while(k<=sz){
int c=span(k);
if(c==k)ans++,c++;
k=c;
}
return ans;
}
int swap_seats(int a, int b) {
swap(R_[a],R_[b]);
swap(C_[a],C_[b]);
act(a),act(b);
return qry();
}
