#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 3000;
struct BIT {
int tree[B];
void add (int x, int y) {
for (; x < B; x += x & (-x)) {
tree[x] += y;
}
}
int get (int x) {
int sum = 0;
for (; x > 0; x -= x & (-x)) {
sum += tree[x];
}
return sum;
}
} cur;
ll count_rectangles (vector <vector <int>> a) {
int n = a.size(), m = a[0].size();
vector <int> ii[n][m], jj[n][m];
vector <pair <int, int>> gg[n][m], hh[n][m];
for (int i = 0; i < n; i++) {
stack <int> cur;
cur.push(0);
for (int j = 1; j < m; j++) {
while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
cur.pop();
}
if (!cur.empty() && cur.top() + 1 <= j - 1) {
ii[i][j - 1].push_back(cur.top() + 1);
}
cur.push(j);
}
while (!cur.empty()) {
cur.pop();
}
cur.push(m - 1);
for (int j = m - 2; j >= 0; j--) {
while (!cur.empty() && a[i][j] > a[i][cur.top()]) {
cur.pop();
}
if (!cur.empty() && j + 1 <= cur.top() - 1 && a[i][j] != a[i][cur.top()]) {
ii[i][cur.top() - 1].push_back(j + 1);
}
cur.push(j);
}
}
for (int i = 0; i < m; i++) {
stack <int> cur;
cur.push(0);
for (int j = 1; j < n; j++) {
while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
cur.pop();
}
if (!cur.empty() && cur.top() + 1 <= j - 1) {
jj[j - 1][i].push_back(cur.top() + 1);
}
cur.push(j);
}
while (!cur.empty()) {
cur.pop();
}
cur.push(n - 1);
for (int j = n - 2; j >= 0; j--) {
while (!cur.empty() && a[j][i] > a[cur.top()][i]) {
cur.pop();
}
if (!cur.empty() && j + 1 <= cur.top() - 1 && a[j][i] != a[cur.top()][i]) {
jj[cur.top() - 1][i].push_back(j + 1);
}
cur.push(j);
}
}
map <pair <int, int>, int> last, dd;
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
for (auto k : ii[i][j]) {
if (last[{k, j}] == i - 1) {
dd[{k, j}]++;
} else {
dd[{k, j}] = 1;
}
gg[i][j].push_back({j - k + 1, dd[{k, j}]});
last[{k, j}] = i;
}
}
}
last.clear(); dd.clear();
for (int j = 1; j + 1 < m; j++) {
for (int i = 1; i + 1 < n; i++) {
for (auto k : jj[i][j]) {
if (last[{k, i}] == j - 1) {
dd[{k, i}]++;
} else {
dd[{k, i}] = 1;
}
hh[i][j].push_back({i - k + 1, dd[{k, i}]});
last[{k, i}] = j;
}
}
}
ll ans = 0;
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
sort(gg[i][j].begin(), gg[i][j].end(), [&] (pair <int, int> x, pair <int, int> y) {
return x.second < y.second;
});
sort(hh[i][j].begin(), hh[i][j].end());
reverse(hh[i][j].begin(), hh[i][j].end());
int ptr = 0;
vector <int> d;
for (auto a : gg[i][j]) {
while (!hh[i][j].empty() && hh[i][j].back().first <= a.second) {
cur.add(hh[i][j].back().second, 1);
d.push_back(hh[i][j].back().second);
hh[i][j].pop_back();
}
ans += cur.get(B - 1) - cur.get(a.first - 1);
}
for (auto j : d) {
cur.add(j, -1);
}
}
}
return ans;
}
