#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
const int N = 2505;
vector<array<int, 3>> vec[N][N];
int lst[2][N][N], fst[2][N][N], ft[N];
void Add(int i, int v){
for (; i < N; i += i & -i)
ft[i] += v;
}
int get(int i, int ans = 0){
for (; i; i -= i & -i)
ans += ft[i];
return ans;
}
void upd(int t, int l, int r, int j){
if (r - l <= 1)
return;
if (lst[t][l][r] != j)
fst[t][l][r] = j;
lst[t][l][r] = j + 1;
if (t == 0)
vec[r-1][j].push_back({lst[t][l][r] - fst[t][l][r], r - l - 1, 1});
else
vec[j][r-1].push_back({r - l - 1, lst[t][l][r] - fst[t][l][r], 0});
}
long long count_rectangles(vector<vector<int>> A){
int n = A.size(), m = A[0].size();
for (int j=1;j<m-1;j++){
vector<int> v = {0};
for (int i=1;i<n;i++){
while (v.size() > 0 and A[v.back()][j] < A[i][j]){
upd(0, v.back(), i, j);
v.pop_back();
}
if (v.size() > 0 and A[v.back()][j] >= A[i][j])
upd(0, v.back(), i, j);
if (v.size() > 0 and A[v.back()][j] == A[i][j])
v.pop_back();
v.push_back(i);
}
}
for (int i=1;i<n-1;i++){
vector<int> v = {0};
for (int j=1;j<m;j++){
while (v.size() > 0 and A[i][v.back()] < A[i][j]){
upd(1, v.back(), j, i);
v.pop_back();
}
if (v.size() > 0 and A[i][v.back()] >= A[i][j])
upd(1, v.back(), j, i);
if (v.size() > 0 and A[i][v.back()] == A[i][j])
v.pop_back();
v.push_back(j);
}
}
long long Ans = 0;
for (int i=1;i<n;i++){
for (int j=1;j<m;j++){
for (int k=0;k<vec[i][j].size();k++)
vec[i][j][k][1] *= -1;
sort(rbegin(vec[i][j]), rend(vec[i][j]));
for (int k=0;k<vec[i][j].size();k++)
vec[i][j][k][1] *= -1;
for (auto [a, b, t] : vec[i][j]){
if (t == 1)
Add(b, 1);
else
Ans += get(b);
}
for (auto [a, b, t] : vec[i][j]){
if (t == 1)
Add(b, -1);
}
}
}
return Ans;
}
