#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sec second
ll bit[2505];
ll N, M;
void upd(ll idx, ll val) {
for (; idx <= M; idx += idx & -idx) bit[idx] += val;
}
ll get(ll idx) {
ll ans = 0;
for (; idx >= 1; idx -= idx & -idx) ans += bit[idx];
return ans;
}
ll query(ll l, ll r) {
return get(r) - get(l - 1);
}
long long count_rectangles(vector<vector<int>> a) {
N = a.size();
M = a[0].size();
pair<ll, ll> lst[max(N, M) + 1][max(N, M)];
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
lst[i][j] = {0, -1};
}
}
vector <pair<ll, ll>> h[N][M], v[N][M];
for (int i = 0; i < N; i++) {
stack <ll> stk;
for (int j = 0; j < M; j++) {
bool sm = 0;
while (!stk.empty() && a[i][stk.top()] <= a[i][j]) {
sm |= (a[i][stk.top()] == a[i][j]);
if (j - stk.top() >= 2) {
ll sz;
if (lst[stk.top()][j].sec != i - 1) {
sz = 1;
}
else {
sz = lst[stk.top()][j].fi + 1;
}
lst[stk.top()][j] = {sz, i};
h[i][j].push_back({sz, j - stk.top() - 1});
}
stk.pop();
}
if (!stk.empty() && !sm) {
if (j - stk.top() >= 2) {
ll sz;
if (lst[stk.top()][j].sec != i - 1) {
sz = 1;
}
else {
sz = lst[stk.top()][j].fi + 1;
}
lst[stk.top()][j] = {sz, i};
h[i][j].push_back({sz, j - stk.top() - 1});
}
}
sort(h[i][j].begin(), h[i][j].end());
stk.push(j);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
lst[i][j] = {0, -1};
}
}
for (int j = 0; j < M; j++) {
stack <ll> stk;
for (int i = 0; i < N; i++) {
bool sm = 0;
while (!stk.empty() && a[stk.top()][j] <= a[i][j]) {
sm |= (a[stk.top()][j] == a[i][j]);
if (i - stk.top() >= 2) {
ll sz;
if (lst[stk.top()][i].sec != j - 1) {
sz = 1;
}
else {
sz = lst[stk.top()][i].fi + 1;
}
lst[stk.top()][i] = {sz, j};
v[i][j].push_back({i - stk.top() - 1, sz});
}
stk.pop();
}
if (!stk.empty() && !sm) {
if (i - stk.top() >= 2) {
ll sz;
if (lst[stk.top()][i].sec != j - 1) {
sz = 1;
}
else {
sz = lst[stk.top()][i].fi + 1;
}
lst[stk.top()][i] = {sz, j};
v[i][j].push_back({i - stk.top() - 1, sz});
}
}
sort(v[i][j].begin(), v[i][j].end());
// cout << i << " " << j << "\n";
// for (auto [x, y] : v[i][j]) cout << x << " " << y << "\n";
// cout << "\n";
stk.push(i);
}
}
/*
H -> {b, a}
V -> {c, d}
b >= c
d >= a
*/
ll ans = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = 1; j < M; j++) {
ll pt = -1;
for (auto [b, a] : h[i][j]) {
while (pt + 1 < (ll)v[i + 1][j - 1].size()) {
auto [c, d] = v[i + 1][j - 1][pt + 1];
if (b >= c) {
upd(d, 1);
pt++;
}
else {
break;
}
}
ans += query(a, M);
}
for (int k = 0; k <= pt; k++) {
auto [c, d] = v[i + 1][j - 1][k];
upd(d, -1);
}
}
}
return ans;
}
