#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
struct SegTree {
int st[4 * N];
SegTree(int n) {
for (int i = 0; i < 4 * n; i++) st[i] = 0;
}
void update(int v, int tl, int tr, int idx, int add) {
if (tl == tr) {
st[v] += add;
return;
}
int mid = tl + (tr - tl) / 2;
if (idx <= mid) update(2 * v, tl, mid, idx, add);
else update(2 * v + 1, mid + 1, tr, idx, add);
st[v] = st[2 * v] + st[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) return st[v];
int mid = tl + (tr - tl) / 2;
return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
}
};
long long int count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<int> dp_col[N][N];
for (int i = 0; i < m; i++) {
set<int> col;
col.insert(-1);
col.insert(n);
vector<tuple<int,int,int>> b;
for (int j = 0; j < n; j++) b.emplace_back(-a[j][i], j, i);
sort(b.begin(), b.end());
int p = 0;
while (p < n) {
int curr = get<0>(b[p]);
int start = p;
while (p < n && get<0>(b[p]) == curr) {
auto [_, x, y] = b[p++];
col.insert(x);
}
for (int j = start; j < p; j++) {
auto [_, x, y] = b[j];
auto it = col.find(x);
it--;
if (*it != -1 && x - *it > 1) {
int l = (*it) + 1;
int r = x - 1;
dp_col[l][y].push_back(-r);
}
it++;
it++;
if (*it != n && (*it) - x > 1) {
int l = x + 1;
int r = (*it) - 1;
dp_col[l][y].push_back(-r);
}
}
}
}
SegTree st(m);
long long int ans = 0;
unordered_map<int,int> row_nxt[N];
for (int i = n - 2; i > 0; i--) {
unordered_map<int,int> row_curr[N];
set<int> row;
row.insert(-1);
row.insert(m);
vector<tuple<int,int,int>> b;
for (int j = 0; j < m; j++) b.emplace_back(-a[i][j], i, j);
sort(b.begin(), b.end());
int p = 0;
while (p < m) {
int curr = get<0>(b[p]);
int start = p;
while (p < m && get<0>(b[p]) == curr) {
auto [_, x, y] = b[p++];
row.insert(y);
}
for (int j = start; j < p; j++) {
auto [_, x, y] = b[j];
auto it = row.find(y);
it--;
if (*it != -1 && y - *it > 1) {
int l = (*it) + 1;
int r = y - 1;
row_curr[l][r] = -x;
}
it++;
it++;
if (*it != m && (*it) - y > 1) {
int l = y + 1;
int r = (*it) - 1;
row_curr[l][r] = -x;
}
}
}
map<int,int> nxt;
for (int j = m - 2; j > 0; j--) {
map<int,int> curr;
for (auto idx: dp_col[i][j]) {
curr[idx] = j;
}
if (j + 2 < m) {
for (auto [idx, _]: curr) {
if (nxt.count(idx)) curr[idx] = nxt[idx];
}
}
vector<pair<int,int>> order;
for (auto [idx, _]: row_curr[j]) {
if (i + 2 < n && row_nxt[j].count(idx)) row_curr[j][idx] = row_nxt[j][idx];
order.emplace_back(row_curr[j][idx], idx);
}
sort(order.begin(), order.end());
int p = 0;
for (auto [idx, r]: curr) {
while (p < order.size() && order[p].first <= idx) {
st.update(1, 0, m - 1, order[p++].second, 1);
}
ans += st.query(1, 0, m - 1, j, r);
}
while (--p >= 0) st.update(1, 0, m - 1, order[p].second, -1);
for (int j = 0; j < m; j++) row_nxt[j] = move(row_curr[j]);
nxt = move(curr);
}
}
return ans;
}
