#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H, W;
vector<int> R, C;
vector<vector<int>> A;
const int INF = 1e9;
typedef pair<int,int> P;
struct SegTree {
struct Node {
int sum[3];//0, 1, 2
int cnt;
Node(int _c, int s1, int s2, int s3) {
cnt = _c;
sum[0] = s1;
sum[1] = s2;
sum[2] = s3;
}
Node() {
cnt = sum[0] = sum[1] = sum[2] = 0;
}
};
vector<Node> seg; // max, min
int MAX;
void init(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y, int cnt) {
Node c;
c.cnt = cnt;
c.sum[0] = c.sum[1] = c.sum[2] = 0;
for(int i = 0; i+cnt < 3; i++) {
c.sum[i+cnt] += x.sum[i] + y.sum[i];
}
return c;
}
void add(int s, int e, int k, int n, int ns, int ne) {
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].cnt += k;
}
else {
int mid = ns + ne >> 1;
add(s,e,k,2*n,ns,mid);
add(s,e,k,2*n+1,mid,ne);
}
assert(seg[n].cnt >= 0);
if(ne==ns+1) {
seg[n].sum[0] = seg[n].sum[1] = seg[n].sum[2] = 0;
if(seg[n].cnt < 3) seg[n].sum[seg[n].cnt] = 1;
}
else {
seg[n] = f(seg[2*n],seg[2*n+1], seg[n].cnt);
}
}
void add(int s, int e, int k) {
add(s,e,k,1,0,MAX/2);
}
int sum() {
return seg[1].sum[2];
}
};
//int chk[1000005];
SegTree tree;
int B[1000005];
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C) {
H = _H;
W = _W;
R = _R;
C = _C;
A.resize(H);
int i, j;
for(i=0;i<H;i++) A[i].resize(W);
for(i=0;i<R.size();i++) {
A[R[i]][C[i]] = i;
}
for(i=0;i<W;i++) B[C[i]] =i;
tree.init(W+3);
for(i=0;i+1<W;i++) {
int a = min(B[i],B[i+1]);
int b = max(B[i],B[i+1]);
tree.add(a, b, 1);
}
tree.add(B[0], W, 1);
tree.add(B[W-1], W, 1);
}
int dx[2] = {1,-1};
bool in(int x) {
return 0 <=x && x < W;
}
int swap_seats(int a, int b) {
if(C[a]>C[b]) swap(a, b);
if(1==0) {
int i;
for(i=0;i<1;i++) {
int a2 = C[a] - 1;
if(in(a2)) {
tree.add(min(a,B[a2]),max(a,B[a2]),-1);
}
else {
tree.add(a, W, -1);
}
}
for(i=0;i<1;i++) {
int b2 = C[b] + 1;
if(in(b2)) {
tree.add(min(b,B[b2]),max(b,B[b2]),-1);
}
else {
tree.add(b, W, -1);
}
}
int v = B[C[b]];
B[C[b]] = B[C[a]];
B[C[a]] = v;
v = C[a];
C[a] = C[b];
C[b] = v;
for(i=0;i<1;i++) {
int a2 = C[a] + 1;
if(in(a2)) {
tree.add(min(a,B[a2]),max(a,B[a2]),1);
}
else {
tree.add(a, W, 1);
}
}
for(i=0;i<1;i++) {
int b2 = C[b] - 1;
if(in(b2)) {
tree.add(min(b,B[b2]),max(b,B[b2]),1);
}
else {
tree.add(b, W, 1);
}
}
}
else {
int i;
for(i=0;i<2;i++) {
int a2 = C[a] + dx[i];
if(in(a2)) {
tree.add(min(a,B[a2]),max(a,B[a2]),-1);
}
else {
tree.add(a, W, -1);
}
}
for(i=0;i<2;i++) {
int b2 = C[b] + dx[i];
if(in(b2)) {
tree.add(min(b,B[b2]),max(b,B[b2]),-1);
}
else {
tree.add(b, W, -1);
}
}
int v = B[C[b]];
B[C[b]] = B[C[a]];
B[C[a]] = v;
v = C[a];
C[a] = C[b];
C[b] = v;
for(i=0;i<2;i++) {
int a2 = C[a] + dx[i];
if(in(a2)) {
tree.add(min(a,B[a2]),max(a,B[a2]),1);
}
else {
tree.add(a, W, 1);
}
}
for(i=0;i<2;i++) {
int b2 = C[b] + dx[i];
if(in(b2)) {
tree.add(min(b,B[b2]),max(b,B[b2]),1);
}
else {
tree.add(b, W, 1);
}
}
}
return tree.sum();
}
