#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
const int MX = 2505;
ll ans = 0;
int n,m;
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
vector<pii> row_seg[MX][MX],col_seg[MX][MX];
map<int,int> row_map[MX][MX],col_map[MX][MX];
void check_rectangle(int x1,int y1,int x2,int y2){
if(row_map[y1-1][y2+1].find(x1) == row_map[y1-1][y2+1].end()) return;
if(row_map[y1-1][y2+1][x1] < x2) return;
if(col_map[x1-1][x2+1].find(y1) == col_map[x1-1][x2+1].end()) return;
if(col_map[x1-1][x2+1][y1] < y2) return;
ans++;
}
ll count_rectangles(vector<vi> a) {
n = a.size();
m = a[0].size();
if(n <= 2 or m <= 2) return 0;
REP(i,n){
stack<int> st;
REP(j,m){
gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
}
REP(j,m){
while(st.size() and a[i][st.top()] <= a[i][j]){
gr[i][st.top()] = j;
st.pop();
}
st.push(j);
}
while(!st.empty()) st.pop();
FORD(j,m-1,0){
while(st.size() and a[i][st.top()] <= a[i][j]){
gl[i][st.top()] = j;
st.pop();
}
st.push(j);
}
REP(j,m){
if(gr[i][j] != -1 and gr[i][j] != j+1){
if(row_seg[j][gr[i][j]].empty() or i-1 > row_seg[j][gr[i][j]].back().S){
row_seg[j][gr[i][j]].pb({i,i});
}
else row_seg[j][gr[i][j]].back().S++;
}
if(gl[i][j] != -1 and gl[i][j] != j-1 and gr[i][gl[i][j]] != j){
if(row_seg[gl[i][j]][j].empty() or i-1 > row_seg[gl[i][j]][j].back().S){
row_seg[gl[i][j]][j].pb({i,i});
}
else row_seg[gl[i][j]][j].back().S++;
}
}
}
REP(j,m){
stack<int> st;
REP(i,n){
while(st.size() and a[st.top()][j] <= a[i][j]){
gd[st.top()][j] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
FORD(i,n-1,0){
while(st.size() and a[st.top()][j] <= a[i][j]){
gu[st.top()][j] = i;
st.pop();
}
st.push(i);
}
REP(i,n){
if(gd[i][j] != -1 and gd[i][j] != i+1){
if(col_seg[i][gd[i][j]].empty() or j-1 > col_seg[i][gd[i][j]].back().S){
col_seg[i][gd[i][j]].pb({j,j});
}
else col_seg[i][gd[i][j]].back().S++;
}
if(gu[i][j] != -1 and gu[i][j] != i-1 and gd[gu[i][j]][j] != i){
if(col_seg[gu[i][j]][i].empty() or j-1 > col_seg[gu[i][j]][i].back().S){
col_seg[gu[i][j]][i].pb({j,j});
}
else col_seg[gu[i][j]][i].back().S++;
}
}
}
REP(i,m){
FOR(j,i+2,m){
for(auto x:row_seg[i][j]){
FOR(y,x.F,x.S+1){
row_map[i][j][y] = x.S;
}
}
row_seg[i][j].clear();
}
}
REP(i,n){
FOR(j,i+2,n){
for(auto x:col_seg[i][j]){
FOR(y,x.F,x.S+1){
col_map[i][j][y] = x.S;
}
}
col_seg[i][j].clear();
}
}
vector<vi> bruh;
FOR(i,1,n-1){
FOR(j,1,m-1){
// topleft
if(gr[i][j-1] != -1 and gd[i-1][j] != -1){
bruh.pb({i,j,gd[i-1][j]-1,gr[i][j-1]-1});
}
// topright
if(gl[i][j+1] != -1 and gd[i-1][j] != -1){
bruh.pb({i,gl[i][j+1]+1,gd[i-1][j]-1,j});
}
// bottomleft
if(gr[i][j-1] != -1 and gu[i+1][j] != -1){
bruh.pb({gu[i+1][j]+1,j,i,gr[i][j-1]-1});
}
// bottomright
if(gl[i][j+1] != -1 and gu[i+1][j] != -1){
bruh.pb({gu[i+1][j]+1,gl[i][j+1]+1,i,j});
}
// clockwise
if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){
bruh.pb({i,j,gd[i-1][gr[i][j-1]-1]-1,gr[i][j-1]-1});
}
// anti-clockwise
if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){
bruh.pb({i,gl[i][j+1]+1,gd[i-1][gl[i][j+1]+1]-1,j});
}
}
}
sort(all(bruh));
REP(i,SZ(bruh)){
if(i == 0 or bruh[i] != bruh[i-1]){
check_rectangle(bruh[i][0],bruh[i][1],bruh[i][2],bruh[i][3]);
}
}
return ans;
}
