#include <bits/stdc++.h>
//#define int long long
using namespace std;
struct Req {
int deb, fin, coeff, id;
};
const int N = 2500 + 42;
vector<Req> req[N];
vector<int> deb[N][N], val;
int n, m, pre[N][N], nb[N][N];
long long count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
for(int i = 1; i < n-1; i++) {
vector<int> maxi;
for(int j = 0; j < m; j++) {
while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
maxi.pop_back();
if(!maxi.empty() && a[i][maxi.back()] != a[i][j] && maxi.back() < j-1)
deb[i][j].push_back(maxi.back());
maxi.push_back(j);
}
maxi.clear();
for(int j = m-1; j > -1; j--) {
while(!maxi.empty() && a[i][maxi.back()] < a[i][j])
maxi.pop_back();
if(!maxi.empty() && j+1 < maxi.back())
deb[i][maxi.back()].push_back(j);
maxi.push_back(j);
}
}
for(int j = 1; j < m-1; j++) {
vector<int> maxi;
for(int i = 0; i < n; i++) {
while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
maxi.pop_back();
if(!maxi.empty() && maxi.back() < i-1) {
if(pre[maxi.back()][i] != j-1)
nb[maxi.back()][i] = 0;
nb[maxi.back()][i]++;
pre[maxi.back()][i] = j;
for(int d : deb[maxi.back()+1][j+1]) {
if(d >= j-nb[maxi.back()][i]) {
int reqId = val.size();
val.push_back(-(i-maxi.back()-1));
req[maxi.back()+1].push_back({d, j+1, -1, reqId});
req[i].push_back({d, j+1, 1, reqId});
}
}
}
maxi.push_back(i);
}
maxi.clear();
for(int i = n-1; i > -1; i--) {
while(!maxi.empty() && a[maxi.back()][j] < a[i][j])
maxi.pop_back();
if(!maxi.empty() && i+1 < maxi.back() && a[maxi.back()][j] != a[i][j]) {
if(pre[i][maxi.back()] != j-1)
nb[i][maxi.back()] = 0;
nb[i][maxi.back()]++;
pre[i][maxi.back()] = j;
for(int d : deb[i+1][j+1]) {
if(d >= j-nb[i][maxi.back()]) {
int reqId = val.size();
val.push_back(-(maxi.back()-i-1));
req[i+1].push_back({d, j+1, -1, reqId});
req[maxi.back()].push_back({d, j+1, 1, reqId});
}
}
}
maxi.push_back(i);
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
nb[i][j] = 0;
for(int i = 1; i < n; i++) {
for(Req r : req[i])
val[r.id] += nb[r.deb][r.fin] * r.coeff;
for(int j = 0; j < m; j++)
for(int d : deb[i][j])
nb[d][j]++;
}
long long ans = 0;
for(int i : val)
if(i == 0)
ans++;
return ans;
}
