#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;
int n,m;
vector<vi> A;
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
vi rows[MX][MX],cols[MX][MX];
vector<pii> row_seg[MX][MX],col_seg[MX][MX];
bool check_rectangle(int x1,int x2,int y1,int y2){
// auto it = lower_bound(all(row_seg[x1-1][x2+1]),make_pair(y1,MX));
// if(it == row_seg[x1-1][x2+1].begin()) return false;
// it--;
// if((*it).S < y2) return false;
// it = lower_bound(all(col_seg[y1-1][y2+1]),make_pair(x1,MX));
// if(it == col_seg[y1-1][y2+1].begin()) return false;
// it--;
// if((*it).S < x2) return false;
// return true;
FOR(i,x1,x2+1){
if(!binary_search(all(rows[y1-1][y2+1]),i)) return false;
}
FOR(i,y1,y2+1){
if(!binary_search(all(cols[x1-1][x2+1]),i)) return false;
}
return true;
}
ll count_rectangles(vector<vi> a) {
n = a.size();
m = a[0].size();
A = a;
if(n <= 2 or m <= 2) return 0;
ll ans = 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);
}
set<pii> s;
REP(j,m){
if(gr[i][j] != -1 and gr[i][j] != j+1) s.insert({j,gr[i][j]});
if(gl[i][j] != -1 and gl[i][j] != j-1) s.insert({gl[i][j],j});
}
for(auto x:s){
// cout << "row: " << i << " -> " << x.F << " " << x.S << "\n";
rows[x.F][x.S].pb(i);
}
}
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);
}
set<pii> s;
REP(i,n){
if(gd[i][j] != -1 and gd[i][j] != i+1) s.insert({i,gd[i][j]});
if(gu[i][j] != -1 and gu[i][j] != i-1) s.insert({gu[i][j],i});
}
for(auto x:s){
cols[x.F][x.S].pb(j);
}
}
REP(i,n){
FOR(j,i+2,n){
REP(k,SZ(rows[i][j])){
if(k == 0 or rows[i][j][k] > rows[i][j][k-1]+1) row_seg[i][j].pb({rows[i][j][k],rows[i][j][k]});
else row_seg[i][j].back().S++;
}
REP(k,SZ(cols[i][j])){
if(k == 0 or cols[i][j][k] > cols[i][j][k-1]+1) col_seg[i][j].pb({cols[i][j][k],cols[i][j][k]});
else col_seg[i][j].back().S++;
}
}
}
FOR(r1,1,n-1){
FOR(r2,r1,n-1){
FOR(c1,1,m-1){
FOR(c2,c1,m-1){
if(check_rectangle(r1,r2,c1,c2)) ans++;
}
}
}
}
return ans;
}
