#include<bits/stdc++.h>
#include "seats.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
vector<int> X, Y;
int N, M;
/*
int solve(){
int mnx = X[0], mxx = X[0];
int mny = Y[0], mxy = Y[0];
int ans = 1;
for(int i = 1; i < N * M; i++){
mnx = min(mnx, X[i]);
mny = min(mny, Y[i]);
mxx = max(mxx, X[i]);
mxy = max(mxy, Y[i]);
ans+= i+1 == (mxx - mnx + 1) * (mxy - mny + 1);
}
return ans;
} */
int val[maxn];
int mx[4 * maxn], cnt[4 * maxn], lz[4 * maxn];
void mrg(int id){
mx[id] = max(mx[2*id], mx[2*id+1]);
cnt[id] = 0;
if(mx[id] == mx[2*id])
cnt[id]+= cnt[2*id];
if(mx[id] == mx[2*id+1])
cnt[id]+= cnt[2*id+1];
}
void build(int l = 0, int r = M, int id = 1){
mx[id] = -l;
cnt[id] = 1;
if(r-l == 1)
return;
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id+1);
}
void shift(int l, int r, int id = 1){
mx[id]+= lz[id];
if(r-l > 1)
lz[2*id]+= lz[id], lz[2*id+1]+= lz[id];
lz[id] = 0;
}
void add(int pos, int x, int l = 0, int r = M, int id = 1){
shift(l, r, id);
if(r <= pos)
return;
if(pos <= l){
lz[id] = x;
shift(l, r, id);
return;
}
int mid = (l+r) >> 1;
add(pos, x, l, mid, 2*id);
add(pos, x, mid, r, 2*id+1);
mrg(id);
}
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y){
::N = N, ::M = M, ::X = X, ::Y = Y;
assert(N == 1);
for(int i = 0; i < M; i++)
val[Y[i]] = i;
build();
for(int i = 0; i < M-1; i++)
add(max(val[i], val[i+1]), 1);
}
int swap_seats(int a, int b){
swap(Y[a], Y[b]);
a = Y[a], b = Y[b];
if(a > 0)
add(max(val[a], val[a-1]), -1);
if(a < M-1)
add(max(val[a], val[a+1]), -1);
if(b > 0)
add(max(val[b], val[b-1]), -1);
if(b < M-1)
add(max(val[b], val[b+1]), -1);
swap(val[a], val[b]);
if(a > 0)
add(max(val[a], val[a-1]), 1);
if(a < M-1)
add(max(val[a], val[a+1]), 1);
if(b > 0)
add(max(val[b], val[b-1]), 1);
if(b < M-1)
add(max(val[b], val[b+1]), 1);
return mx[1] == 0 ? cnt[1] : 0;
}
