#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
using namespace std;
template<typename T> struct fenwick {
int n; vector<T> bit;
fenwick(int a) : n(a), bit(a+1) {}
T sum(int pos) {
T s = 0;
for (; pos; s += bit[pos], pos -= pos&-pos);
return s;
}
T query(int l, int r) {
return sum(r+1) - sum(l);
}
void update(int pos, T x) {
pos++;
for (; pos <= n; bit[pos] += x, pos += pos&-pos);
}
};
const int nax = 2505;
short u[nax][nax], d[nax][nax], l[nax][nax], r[nax][nax], st[nax], idx[nax], idx2[nax];
vector<short> who[nax][nax], who2[nax][nax], to[nax][nax], to2[nax][nax];
vector<bool> vis[nax][nax], vis2[nax][nax];
fenwick<int> fw(nax);
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = sz(a), m = sz(a[0]);
for (int i = 0, tp = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
while (tp && a[i][j] >= a[i][st[tp]]) tp--;
l[i][j] = tp ? st[tp] : m + 1;
st[++tp] = j;
}
tp = 0;
for (int j = m-1; j >= 0; j--) {
while (tp && a[i][j] >= a[i][st[tp]]) tp--;
r[i][j] = tp ? st[tp] : -2;
st[++tp] = j;
}
}
for (int i = 0, tp = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
while (tp && a[j][i] >= a[st[tp]][i]) tp--;
u[j][i] = tp ? st[tp] : n + 1;
st[++tp] = j;
}
tp = 0;
for (int j = n-1; j >= 0; j--) {
while (tp && a[j][i] >= a[st[tp]][i]) tp--;
d[j][i] = tp ? st[tp] : -2;
st[++tp] = j;
}
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
int L = l[i][j] + 1, R = r[i][j] - 1;
if (L <= R) who[i][L].emplace_back(R);
int U = u[i][j] + 1, D = d[i][j] - 1;
if (U <= D) who2[U][j].emplace_back(D);
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
sort(all(who[i][j]));
sort(all(who2[i][j]));
who[i][j].erase(unique(all(who[i][j])), who[i][j].end());
who2[i][j].erase(unique(all(who2[i][j])), who2[i][j].end());
vis[i][j].resize(sz(who[i][j]));
vis2[i][j].resize(sz(who2[i][j]));
to[i][j].resize(sz(who[i][j]));
to2[i][j].resize(sz(who2[i][j]));
}
vector<vector<ar<short, 3>>> add(n), rem(n);
for (int i = 0; i < n; i++) { // horizontal
for (int j = 0; j < m; j++) {
for (int k = 0; k < sz(who[i][j]); k++) if (!vis[i][j][k]) {
int r = who[i][j][k];
int d = i;
while (d+1 < n) {
auto it = lower_bound(all(who[d+1][j]), r);
if (it != who[d+1][j].end() && *it == r) d++, vis[d][j][it - who[d][j].begin()] = 1;
else break;
}
for (int z = i; z <= d; z++) {
to[z][j][lower_bound(all(who[z][j]), r) - who[z][j].begin()] = d;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < sz(who2[i][j]); k++) if (!vis2[i][j][k]) {
int d = who2[i][j][k], r = j;
while (r+1 < m) {
auto it = lower_bound(all(who2[i][r+1]), d);
if (it != who2[i][r+1].end() && *it == d) r++, vis2[i][r][it - who2[i][r].begin()] = 1;
else break;
}
for (int z = j; z <= r; z++) {
to2[i][z][lower_bound(all(who2[i][z]), d) - who2[i][z].begin()] = r;
}
}
}
}
ll ans = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
iota(idx, idx + sz(who[i][j]), 0);
sort(idx, idx + sz(who[i][j]), [&](int x, int y) { return who[i][j][x] < who[i][j][y]; });
iota(idx2, idx2 + sz(who2[i][j]), 0);
sort(idx2, idx2 + sz(who2[i][j]), [&](int x, int y) { return to2[i][j][x] < to2[i][j][y]; });
int t = 0;
for (int k = 0; k < sz(who2[i][j]); k++) {
while (t < sz(who[i][j]) && who[i][j][idx[t]] <= to2[i][j][idx2[k]]) {
fw.update(to[i][j][idx[t++]], 1);
}
ans += fw.query(who2[i][j][idx2[k]], nax-1);
}
for (int k = 0; k < t; k++) fw.update(to[i][j][idx[k]], -1);
}
return ans;
}
