#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int n, m;
int r[maxn];
struct node
{
int val, cnt, lz;
node(int a = 0, int b = 0) : val(a), cnt(b)
{
lz = 0;
}
};
node st[4*maxn];
node pull(node &x, node &y)
{
if(x.val< y.val) return x;
if(x.val> y.val) return y;
return node(x.val, x.cnt+y.cnt);
}
void pushdown(int p, int L, int R)
{
if(st[p].lz == 0) return;
st[p].val += st[p].lz;
if(L != R)
{
st[2*p].lz += st[p].lz;
st[2*p+1].lz += st[p].lz;
}
st[p].lz = 0;
}
void build(int p = 1, int L = 0, int R = n-1)
{
if(L == R)
{
st[p] = node(0, 1);
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int dx, int p = 1, int L = 0, int R = n-1)
{
pushdown(p, L, R);
if(i> j || i> R || j< L) return;
if(i<= L && R<= j)
{
st[p].lz += dx;
pushdown(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, 2*p, L, M);
update(i, j, dx, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = n-1)
{
if(i> R || j< L) return node(1e9, 0);
pushdown(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
int tim[maxn];
int tog[maxn];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
m = H;
n = W;
assert(m == 1);
for(int i = 0; i< n; i++)
{
tim[i] = C[i];
tog[C[i]] = i;
}
int prv = 0;
build();
for(int i = 0; i< n; i++)
{
int dat = tim[i];
int y = 0;
if(dat && tog[dat-1]< i) y++;
if(dat+1< n && tog[dat+1]< i) y++;
int cur = prv + 2 - 2*y;
update(i, i, cur);
prv = cur;
}
node kk = ask(0, n-1);
// printf("%d %d\n", kk.val, kk.cnt);
}
void add(int val, int a, int b)
{
// printf("add %d to [%d %d]\n", val, a, b);
int m1 = val?tog[val-1]:1e9;
int m2 = val+1< n?tog[val+1]:1e9;
// printf("%d %d\n", m1, m2);
if(m1> m2) swap(m1, m2);
update(a, min(m1-1, b), 2);
// printf("[%d %d] +2\n", a, min(m1-1, b));
update(max(a, m2), b, -2);
// printf("[%d %d] -2\n", max(a, m2), b);
}
void rem(int val, int a, int b)
{
// printf("remove %d from [%d %d]\n", val, a, b);
int m1 = val?tog[val-1]:1e9;
int m2 = val+1< n?tog[val+1]:1e9;
// printf("%d %d\n", m1, m2);
if(m1> m2) swap(m1, m2);
update(a, min(m1-1, b), -2);
// printf("[%d %d] -2\n", a, min(m1-1, b));
update(max(a, m2), b, 2);
// printf("[%d %d] +2\n", max(a, m2), b);
}
int swap_seats(int a, int b)
{
if(a> b) swap(a, b);
rem(tim[a], a, b-1);
swap(tog[tim[a]], tog[tim[b]]);
add(tim[b], a, b-1);
swap(tim[a], tim[b]);
// printf("tog = ");
// for(int i = 0; i< n; i++) printf("%d ", tog[i]);
// printf("\ntim = ");
// for(int i = 0; i< n; i++) printf("%d ", tim[i]);
// printf("\nf = ");
// for(int i = 0; i< n; i++) printf("%d ", ask(i, i).val);
// printf("\n");
node kk = ask(0, n-1);
if(kk.val == 2) return kk.cnt;
return 0;
}
