#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef array<int, 4> ar4;
const int MAXN = 1e6+5;
const int BLOCK = 1000;
int n;
int points[MAXN];
int num_blocks;
pii rangeval[BLOCK];
pii interval[MAXN];
map<int, vector<int>> occs[BLOCK][2];
void combine(pii &a, pii &b) {
a.first = min(a.first, b.first);
a.second = max(a.second, b.second);
}
void expand(pii &in, int v) {
in.first = min(in.first, v);
in.second = max(in.second, v);
}
void make(int i) {
occs[i][0].clear();
occs[i][1].clear();
pii cur_int(n, 0);
for (int j = i*BLOCK; j < min((i+1)*BLOCK, n); j++) {
expand(cur_int, points[j]);
interval[j] = cur_int;
}
rangeval[i] = cur_int;
for (int j = i*BLOCK; j < min((i+1)*BLOCK, n); j++) {
occs[i][0][interval[j].second-j+1].push_back(interval[j].first);
occs[i][1][interval[j].first+j-1].push_back(interval[j].second);
}
}
int get_ans(pii cur_int, int i) {
int ans = 0;
// >= cur_int.first, r
if (occs[i][0].find(cur_int.second) != occs[i][0].end()) {
vector<int> &v = occs[i][0][cur_int.second];
int mn = -1;
int mx = v.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (v[cur] >= cur_int.first) mx = cur;
else mn = cur;
}
ans += v.size()-mx;
} // <= second, at first
if (occs[i][1].find(cur_int.first) != occs[i][1].end()) {
vector<int> &v = occs[i][1][cur_int.first];
int mn = -1;
int mx = v.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (v[cur] <= cur_int.second) mn = cur;
else mx = cur;
}
ans += mx;
}
return ans;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = W;
assert(H == 1);
num_blocks = (n+BLOCK-1)/BLOCK;
for (int i = 0; i < n; i++) {
points[i] = C[i];
assert(R[i] == 0);
}
for (int i = 0; i < num_blocks; i++) make(i);
}
int swap_seats(int a, int b) {
swap(points[a], points[b]);
make(a/BLOCK);
if (a/BLOCK != b/BLOCK) make(b/BLOCK);
pii vals(points[0], points[0]);
int ans = 0;
for (int i = 0; i < num_blocks; i++) {
ans += get_ans(vals, i);
combine(vals, rangeval[i]);
}
return ans;
}
