//#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct dsu {
vector<int> p, s, l, r;
dsu(int n) : p(n, -1), s(n, 0), l(n), r(n) { for (int i = 0; i < n; i++) l[i] = r[i] = i; };
dsu() :dsu(0) {};
int getp(int v) {
return p[v] == -1 ? v : p[v] = getp(p[v]);
}
void merge(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return;
if (s[a] < s[b]) swap(a, b);
if (s[a] == s[b]) s[a]++;
l[a] = min(l[a], l[b]);
r[a] = max(r[a], r[b]);
p[b] = a;
}
};
const int mx = 5005;
//binary index tree
struct bit {
vector<int> b; int n;
bit(int n) : n(n), b(n, 0) {}
void upd(int i, int v) { for (i++; i <= n; i += i & -i) b[i - 1] += v; }
void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i - 1];return v; }
int q(int l, int r) { return q(r) - q(l - 1); }
} uwu(mx);
long long count_rectangles(vector<vector<int32_t>> a) {
int n = a.size(), m = a[0].size();
vector<vector<map<int, int>>> vert, hori; // idfc
vert = hori = vector<vector<map<int, int>>>(mx, vector<map<int, int>>(mx));
for (int i = 0; i < n; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < m; j++) v.push_back(make_pair((long long)a[i][j], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1]) ac.merge(t - 1, t);
if (t + 1 < m && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (i == 4) {
// cout << t << "bruh " << ac.l[t] << " " << ac.r[t] << endl;
}
if (ac.l[t] && ac.r[t] + 1 < m && a[i][ac.l[t] - 1] > p && a[i][ac.r[t] + 1] > p) {
hori[i][ac.l[t]][ac.r[t] - ac.l[t] + 1] = 1;
}
}
}
for (int i = 0; i < m; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < n; j++) v.push_back(make_pair((int)a[j][i], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1])ac.merge(t - 1, t);
if (t + 1 < n && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (ac.l[t] && ac.r[t] + 1 < n && a[ac.l[t] - 1][i] > p && a[ac.r[t] + 1][i] > p) {
vert[ac.l[t]][i][ac.r[t] - ac.l[t] + 1] = 1;
}
}
}
long long res = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
// cout << i << "," << j << endl;
if (i + 1 < n) {
for (auto& x : hori[i][j]) {
x.second += hori[i + 1][j][x.first];
}
}
if (j + 1 < m) {
for (auto& x : vert[i][j]) {
x.second += vert[i][j + 1][x.first];
}
}
vector<pair<int, int>> bruh;
for (auto& x : vert[i][j]) bruh.push_back(make_pair(x.second, x.first));
sort(bruh.begin(), bruh.end());
int cur = 0;
for (auto& x : hori[i][j]) {
while (cur < bruh.size() && bruh[cur].first < x.first) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
uwu.upd(x.second, 1);
}
while (cur < bruh.size()) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
for (auto& x : hori[i][j]) {
uwu.upd(x.second, -1);
}
}
}
return res;
}
// int main() {
// int a = count_rectangles({ {4, 8, 7, 5, 6},
// { 7, 4, 10, 3, 5 },
// { 9, 7, 20, 14, 2 },
// { 9, 14, 7, 3, 6 },
// { 5, 7, 5, 2, 7 },
// {4, 5, 13, 5, 6} });
// cout << a << endl;
// }
