#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MX=2510;
int n, m;
vii areasHor[MX];
set<int> heights[MX][MX];
ll ans=0;
int oldMLast[MX][MX];
int oldMVal[MX][MX];
vector<pair<ii, int>> queries[MX*4];
set<int> sts[MX];
void addQuery(pair<ii, int> q, int p=0, int l=0, int r=m-1) {
if(q.fi.se < l || q.fi.fi > r) return;
int md=(l+r)/2;
if(l == r || (q.fi.fi <= md && q.fi.se >= md+1)) {
queries[p].pb(q);
return;
}
addQuery(q,p*2+1,l,md);
addQuery(q,p*2+2,md+1,r);
}
void addAns(int i, int p=0, int l=0, int r=m-1) {
if(l == r) {
for(auto q : queries[p]) {
for(int j : heights[i][q.fi.fi]) {
if(j >= q.se) ans++;
}
}
return;
}
int md=(l+r)/2;
if(!queries[p].empty()) {
sts[md] = heights[i][md];
REV(j,l,md) {
sts[j].clear();
set_intersection(sts[j+1].begin(), sts[j+1].end(), heights[i][j].begin(), heights[i][j].end(), inserter(sts[j], sts[j].end()));
}
sts[md+1] = heights[i][md+1];
REP(j,md+2,r+1) {
sts[j].clear();
set_intersection(sts[j-1].begin(), sts[j-1].end(), heights[i][j].begin(), heights[i][j].end(), inserter(sts[j], sts[j].end()));
}
}
for(auto q : queries[p]) {
set<int> s;
int a=q.fi.fi, b=q.fi.se;
set_intersection(sts[a].begin(),sts[a].end(),sts[b].begin(),sts[b].end(),inserter(s,s.end()));
for(int j : s) {
if(j >= q.se) ans++;
}
}
addAns(i,p*2+1,l,md);
addAns(i,p*2+2,md+1,r);
}
long long count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
RE(i,n) {
stack<int> stck;
RE(j,m) {
while(!stck.empty() && a[i][stck.top()] < a[i][j]) {
int v = a[i][stck.top()];
stck.pop();
if(!stck.empty() && v != a[i][stck.top()]) areasHor[i].pb({stck.top()+1,j-1});
}
stck.push(j);
}
}
RE(j,m) {
stack<int> stck;
RE(i,n) {
while(!stck.empty() && a[stck.top()][j] < a[i][j]) {
int v = a[stck.top()][j];
stck.pop();
if(!stck.empty() && v != a[stck.top()][j]) heights[i-1][j].insert(stck.top()+1);
}
stck.push(i);
}
}
RE(i,MX) RE(j,MX) oldMVal[i][j] = -2, oldMLast[i][j] = -2;
RE(i,n) {
RE(j,m*4) queries[j].clear();
for(ii p : areasHor[i]) {
pair<ii, int> ans;
ans.fi = p;
ans.se = i;
if(oldMLast[p.fi][p.se] == i-1) {
ans.se = oldMVal[p.fi][p.se];
} else {
oldMVal[p.fi][p.se] = i;
}
oldMLast[p.fi][p.se] = i;
addQuery(ans);
}
addAns(i);
}
return ans;
}
