#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 2500 + 11;
struct DSU{
int dsu[N], l[N], r[N];
void init(int n){
for(int i = 0; i <= n + 2; i++) dsu[i] = l[i] = r[i] = i;
}
int root(int x){
if(x == dsu[x]) return x;
return dsu[x] = root(dsu[x]);
}
void join(int x, int y){
x = root(x), y = root(y);
if(x == y) return;
dsu[y] = x;
l[x] = min(l[x], l[y]);
r[x] = max(r[x], r[y]);
}
} dsu;
int at(const vector<int>& v, int idx){
if(idx < 0 || idx >= (int) v.size()) return -(1 << 30);
return v[idx];
}
vector<pii> build(const vector<int>& v){
vector<pii> res;
vector<pii> vp; int n = v.size();
for(int i = 0; i < n; i++){
vp.push_back({v[i], i});
}
sort(vp.begin(), vp.end());
dsu.init(n);
for(auto i : vp){
dsu.join(i.se, i.se + 1);
int rt = dsu.root(i.se);
int b_l = dsu.l[rt], b_r = dsu.r[rt] - 1;
if(at(v, b_l - 1) > i.fi && at(v, b_r + 1) > i.fi){
res.push_back({b_l, b_r});
}
}
return res;
}
struct Rect{
int16_t x1, x2, y1, y2;
void pr() { printf("%d %d %d %d\n", x1, x2, y1, y2); }
friend Rect operator+ (const Rect& a, const Rect& b){
return {max(a.x1, b.x1), min(a.x2, b.x2), max(a.y1, b.y1), min(a.y2, b.y2)};
}
};
void split(const vector<Rect>& a, vector<Rect>& al, vector<Rect>& ar, int xm){
for(auto r : a) {
if(r.x1 <= xm) al.push_back(r);
else ar.push_back(r);
}
}
long long ans = 0;
struct BIT2D{
int bit[N][N];
void add(int x, int y, int v){
x++; y++;
for(int i = x; i < N; i += i & -i){
for(int j = y; j < N; j += j & -j){
bit[i][j] += v;
}
}
}
void qry(int x, int y){
x++; y++;
for(int i = x; i; i -= i & -i){
for(int j = y; j; j -= j & -j){
ans += bit[i][j];
}
}
}
} bit2;
struct BIT{
int bit[N];
void add(int x, int v){
x++;
for(int i = x; i < N; i += i & -i){
bit[i] += v;
}
}
void qry(int x){
x++;
for(int i = x; i; i -= i & -i){
ans += bit[i];
}
}
} bit;
vector<int> xs[N * N], ys[N * N];
vector<Rect> xr, yr;
vector<pii> x[N], y[N];
vector<pair<pii, int>> b[N][N];
vector<Rect> vx[N], vy[N];
void solve(vector<pair<pii, int>>& a){
sort(a.begin(), a.end(), [](const pair<pii, int>& x, const pair<pii, int>& y){
if(x.fi.fi != y.fi.fi) return x.fi.fi < y.fi.fi;
if(x.fi.se != y.fi.se) return x.fi.se < y.fi.se;
return x.se < y.se;
});
for(auto r : a){
if(r.se == 0) bit.add(r.fi.se, 1);
else bit.qry(r.fi.se);
}
for(auto r : a){
if(r.se == 0) bit.add(r.fi.se, -1);
}
}
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = a.size(), m = a[0].size(), mx = 0;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) mx = max(mx, a[i][j]);
for(int i = 0; i < n; i++){
vector<int> v; for(int j = 0; j < m; j++) v.push_back(a[i][j]);
x[i] = build(v);
for(pii p : x[i]){
xs[p.fi * m + p.se].push_back(i);
}
}
for(int i = 0; i < m * m; i++){
int x1 = i / m, x2 = i % m; if(x1 > x2) continue;
int y1 = -2, y2 = -2;
for(auto j : xs[i]){
if(j == y2 + 1){
y2++;
}else{
if(y1 != -2) xr.push_back({x1, x2, y1, y2});
y1 = y2 = j;
}
}
if(y1 != -2) xr.push_back({x1, x2, y1, y2});
}
for(int j = 0; j < m; j++){
vector<int> v; for(int i = 0; i < n; i++) v.push_back(a[i][j]);
y[j] = build(v);
for(pii p : y[j]){
ys[p.fi * n + p.se].push_back(j);
}
}
for(int i = 0; i < n * n; i++){
int y1 = i / n, y2 = i % n; if(y1 > y2) continue;
int x1 = -2, x2 = -2;
for(auto j : ys[i]){
if(j == x2 + 1){
x2++;
}else{
if(x1 != -2) yr.push_back({x1, x2, y1, y2});
x1 = x2 = j;
}
}
if(x1 != -2) yr.push_back({x1, x2, y1, y2});
}
for(auto& r : xr){
for(int y1 = r.y1; y1 <= r.y2; y1++){
b[r.x1][y1].push_back({{r.x2, n - 1 - r.y2}, 0});
}
}
for(auto& r : yr){
for(int x1 = r.x1; x1 <= r.x2; x1++){
b[x1][r.y1].push_back({{r.x2, n - 1 - r.y2}, 1});
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
solve(b[i][j]);
}
}
return ans;
}
