#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> stRow, stCol, lastRow, lastCol, cntRow, cntCol;
int tree[2525];
void add(int x, int v)
{
for (int i = x; i <= 2500; i += i & -i)
tree[i] += v;
}
int get(int x)
{
int res = 0;
for (int i = x; i; i -= i & -i)
res += tree[i];
return res;
}
int solve(vector<pair<int, int>> &rows, vector<pair<int, int>> &cols)
{
int res = 0, i = 0;
sort(rows.begin(), rows.end());
for (auto u : rows)
{
while (i < cols.size() && cols[i].first <= u.first)
add(cols[i++].second, 1);
res += i - get(u.second - 1);
}
for (int j = 0; j < i; j++)
add(cols[j].second, -1);
return res;
}
long long count_rectangles(vector<vector<int>> a)
{
int m = a.size(), n = a[0].size();
stRow = vector<vector<int>>(m, vector<int>(1, 0));
stCol = vector<vector<int>>(n, vector<int>(1, 0));
lastRow = vector<vector<int>>(m, vector<int>(m, -1));
lastCol = vector<vector<int>>(n, vector<int>(n, -1));
cntRow = vector<vector<int>>(m, vector<int>(m, 0));
cntCol = vector<vector<int>>(n, vector<int>(n, 0));
long long ans = 0;
for (int i = 0; i < m - 1; i++)
for (int j = 0; j < n - 1; j++)
{
// row
int hasEqual = 0;
vector<pair<int, int>> cols;
while (!stRow[i].empty())
{
int k = stRow[i].back();
if (!hasEqual)
{
if (lastCol[k][j + 1] + 1 == i) cntCol[k][j + 1]++;
else cntCol[k][j + 1] = 1;
lastCol[k][j + 1] = i;
if (j > k)
cols.push_back({j - k, cntCol[k][j + 1]});
}
if (a[i][j + 1] < a[i][k])
break;
if (a[i][j + 1] == a[i][k])
hasEqual = 1;
stRow[i].pop_back();
}
stRow[i].push_back(j + 1);
// col
hasEqual = 0;
vector<pair<int, int>> rows;
while (!stCol[j].empty())
{
int k = stCol[j].back();
if (!hasEqual)
{
if (lastRow[k][i + 1] + 1 == j) cntRow[k][i + 1]++;
else cntRow[k][i + 1] = 1;
lastRow[k][i + 1] = j;
if (i > k)
rows.push_back({cntRow[k][i + 1], i - k});
}
if (a[i + 1][j] < a[k][j])
break;
if (a[i + 1][j] == a[k][j])
hasEqual = 1;
stCol[j].pop_back();
}
stCol[j].push_back(i + 1);
ans += solve(rows, cols);
}
return ans;
}
