#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#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 FOR(a,b) for(auto& a : b)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
const int MX=2502;
int n, m;
vi difW[MX][MX];
vi difH[MX][MX];
int maxW[MX][MX];
int maxH[MX][MX];
vii lastW[MX][MX];
vii lastH[MX][MX];
long long count_rectangles(vector<vi> a) {
n = a.sz; m = a[0].sz;
RE(i,n) {
stack<int> stck;
RE(j,m) {
while(!stck.empty() && a[i][stck.top()] < a[i][j]) {
stck.pop();
if(!stck.empty()) {
difH[i][stck.top()+1].pb(j-stck.top()-1);
}
}
if(!stck.empty() && a[i][stck.top()] == a[i][j])
stck.pop();
stck.push(j);
}
}
RE(j,m) {
stack<int> stck;
RE(i,n) {
while(!stck.empty() && a[stck.top()][j] < a[i][j]) {
stck.pop();
if(!stck.empty()) {
difW[stck.top()+1][j].pb(i-stck.top()-1);
}
}
if(!stck.empty() && a[stck.top()][j] == a[i][j])
stck.pop();
stck.push(i);
}
}
ll ans = 0;
RE(i,n) RE(j,m) maxW[i][j] = maxH[i][j] = 0;
REV(i,0,n) {
REV(j,0,m) {
FOR(w,difW[i][j]) {
maxH[i][w]++;
lastH[i][j].pb({w,maxH[i][w]});
}
FOR(p,lastH[i][j+1]) {
if(maxH[i][p.fi] == p.se)
maxH[i][p.fi] = 0;
}
FOR(h,difH[i][j]) {
maxW[j][h]++;
lastW[i][j].pb({h,maxW[j][h]});
}
FOR(p,lastW[i+1][j]) {
if(maxW[j][p.fi] == p.se)
maxW[j][p.fi] = 0;
}
FOR(w,difW[i][j]) FOR(h,difH[i][j]) {
if(maxW[j][h] >= w && maxH[i][w] >= h)
ans++;
}
}
}
return ans;
}
