#include <bits/stdc++.h>
using namespace std;
struct Req {
bool isUpd;
int x, y;
};
const int N = 2500 + 42, M = 1 << 12;
vector<int> val;
vector<pair<int, int>> fin[N][N][2];
int n, m, pre[N][N], nb[N][N], sum[2*M];
inline int add(int l, int r, int i) {
if(pre[l][r] != i-1)
nb[l][r] = 0;
pre[l][r] = i;
return ++nb[l][r];
}
void upd(int i, int v) {
i += M;
while(i) {
sum[i] += v;
i >>= 1;
}
}
int getVal(int i) {
i += M;
int ans = sum[i];
while(i) {
if(i & 1)
ans += sum[i-1];
i >>= 1;
}
return ans;
}
long long count_rectangles(vector<vector<int>> a) {
n = (int)a.size();
m = (int)a[0].size();
for(int i = n-2; i > 0; 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)
fin[i][maxi.back()+1][0].push_back({j-1, add(maxi.back()+1, j-1, n-i)-1});
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())
fin[i][j+1][0].push_back({maxi.back()-1, add(j+1, maxi.back()-1, n-i)-1});
maxi.push_back(j);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
nb[i][j] = pre[i][j] = 0;
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() && a[maxi.back()][j] != a[i][j] && maxi.back() < i-1)
fin[maxi.back()+1][j][1].push_back({i-1, add(maxi.back()+1, i-1, j)-1});
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())
fin[i+1][j][1].push_back({maxi.back()-1, add(i+1, maxi.back()-1, j)-1});
maxi.push_back(i);
}
}
int ans = 0;
for(int i = 1; i < n-1; i++) {
for(int j = 1; j < m-1; j++) {
vector<Req> req;
for(auto pii : fin[i][j][0])
req.push_back({true, pii.first - j, pii.second});
for(auto pii : fin[i][j][1])
req.push_back({false, pii.second, pii.first - i});
sort(req.begin(), req.end(),
[](Req a, Req b) {
if(a.y == b.y)
return a.isUpd && !b.isUpd;
return a.y > b.y;
});
for(Req q : req) {
if(q.isUpd)
upd(q.x, 1);
else
ans += getVal(q.x);
}
for(Req q : req)
if(q.isUpd)
upd(q.x, -1);
}
}
return ans;
}
