#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " = " << a << endl
struct x{
int fin;
int minimo;
int cantmin;
};
vector<x> ST;
int id[1000002],arr[1000002];
int base,n;
bool subtask;
void imprime(int pos) {
cout << pos << " " << ST[pos].cantmin << " " << ST[pos].minimo << " " << ST[pos].fin << endl;
}
void mezcla(int nodo) {
int hizq, hder, dif;
hizq = nodo*2;
hder = (nodo*2)+1;
dif = ST[hizq].minimo - (ST[hder].minimo + ST[hizq].fin);
if (dif == 0) {
ST[nodo].cantmin = ST[hizq].cantmin + ST[hder].cantmin;
ST[nodo].minimo = ST[hizq].minimo;
ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
}
else if (dif > 0) {
ST[nodo].cantmin = ST[hder].cantmin;
ST[nodo].minimo = ST[hizq].fin + ST[hder].minimo;
ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
}
else {
ST[nodo].cantmin = ST[hizq].cantmin;
ST[nodo].minimo = ST[hizq].minimo;
ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
if (H == 1) {
subtask = true;
base = 1;
n = H*W;
while (base < n) base*=2;
ST.resize(base*2);
rep(i,0,n) arr[i] = n+1;
rep(i,0,n-1) {
id[i] = C[i];
arr[C[i]] = i;
if (C[i] == 0) {
if (arr[C[i]] > arr[C[i]+1]) ST[base+i] = {0,0,1};
else ST[base+i] = {2,2,1};
}
else if (C[i] == n-1) {
if (arr[C[i]] > arr[C[i]-1]) ST[base+i] = {0,0,1};
else ST[base+i] = {2,2,1};
}
else {
if (arr[C[i]] > arr[C[i]-1] && arr[C[i]] > arr[C[i]+1]) ST[base+i] = {-2,-2,1};
else if (arr[C[i]] < arr[C[i]-1] && arr[C[i]] < arr[C[i]+1]) ST[base+i] = {2,2,1};
else ST[base+i] = {0,0,1};
}
}
for (int j = base-1; j > 0; j--) mezcla(j);
}
}
void checa(int pos) {
if (pos >= n || pos < 0) return;
if (pos == 0) {
if (arr[pos] > arr[pos+1]) ST[base + arr[pos]] = {0,0,1};
else ST[base + arr[pos]] = {2,2,1};
}
else if (pos == n-1) {
if (arr[pos] > arr[pos-1]) ST[base + arr[pos]] = {0,0,1};
else ST[base + arr[pos]] = {2,2,1};
}
else {
if (arr[pos] > arr[pos-1] && arr[pos] > arr[pos+1]) ST[base + arr[pos]] = {-2,-2,1};
else if (arr[pos] < arr[pos-1] && arr[pos] < arr[pos+1]) ST[base + arr[pos]] = {2,2,1};
else ST[base + arr[pos]] = {0,0,1};
}
pos = base + arr[pos];
pos >>= 1;
while (pos > 0) {
mezcla(pos);
pos >>= 1;
}
}
int swap_seats(int a, int b) {
if(subtask) {
swap(arr[id[a]], arr[id[b]]);
swap(id[a], id[b]);
checa(id[a]-1);
checa(id[a]);
checa(id[a]+1);
checa(id[b]-1);
checa(id[b]);
checa(id[b]+1);
return ST[1].cantmin;
}
return 2;
}
