#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int,int> ii;
int Left[2505][2505]; ///Left[r][c]: Left boundary from (r,c) provided (r,c) < (Left[r][c],c)
int Right[2505][2505]; ///Right[r][c]: Right boundary from (r,c) provided (r,c) < (Right[r][c],c)
static vector<int> Up[2505][2505]; ///Up[r][c]: All upper boundary from (r,c);
static vector<int> LeftRight[2505][2505]; ///LeftRight[L][R]: rows that [L,R] form a good pair
static vector<int> UpDown[2505][2505]; ///Updown[T][D]: columns that [T,D] form a good pair
inline int verify(int T, int B, int L, int R){ ///check if the rectangle enclosed by T, B, L, R is good (T, B, L, R are excluded)
int ans = 1;
///number of rows between T and B (both exclusive) that form good pairs (L,R)
if(lower_bound(all(LeftRight[L][R]), B) - upper_bound(all(LeftRight[L][R]), T) != (B - T - 1)) ans = 0;
///number of cols between L and R (both exclusive) that form good pairs (T,B)
if(lower_bound(all(UpDown[T][B]), R) - upper_bound(all(UpDown[T][B]), L) != (R - L - 1)) ans = 0;
return ans;
}
long long count_rectangles(vector<vector<int> > arr) {
int rows = arr.size();
int cols = arr[0].size();
for(int r = 0;r < rows;r++){
for(int c = 0;c < cols;c++){
Left[r][c] = -1;
Right[r][c] = -1;
}
}
for(int r = 0;r < rows;r++){
stack<ii> s; s.push(ii(1e9,-1));
for(int i = 0;i < cols;i++){
while(true){
ii back = s.top();
if(back.second != -1 && back.second != i - 1){
int L = s.top().second;
int R = i;
LeftRight[L][R].push_back(r);
if(arr[r][L] > arr[r][R]) Left[r][R] = L;
else Right[r][L] = R;
}
if(s.top().first >= arr[r][i]){
if(s.top().first == arr[r][i]) s.pop();
break;
}
s.pop();
}
s.push(ii(arr[r][i],i));
}
}
for(int c = 0;c < cols;c++){
stack<ii> s; s.push(ii(1e9,-1));
for(int i = 0;i < rows;i++){
while(true){
ii back = s.top();
if(back.second != -1 && back.second != i - 1){
int T = s.top().second;
int B = i;
UpDown[T][B].push_back(c);
Up[B][c].push_back(T);
}
if(s.top().first >= arr[i][c]){
if(s.top().first == arr[i][c]) s.pop();
break;
}
s.pop();
}
s.push(ii(arr[i][c],i));
}
}
for(int r = 0;r < rows;r++){
for(int c = 0;c < cols;c++){
sort(Up[r][c].begin(),Up[r][c].end());
}
}
int ans = 0;
for(int r = 1;r < rows - 1;r++){
for(int c = 1;c < cols - 1;c++){
if(Right[r][c-1] != -1){
int B = r + 1;
int L = c - 1;
int R = Right[r][L];
for(int i = (int)Up[B][c].size() - 1;i >= 0;i--){
int T = Up[B][c][i];
if(verify(T,B,L,R)) ans++;
else break;
}
}
if(Left[r][c+1] != -1){
int B = r + 1;
int R = c + 1;
int L = Left[r][R];
for(int i = (int)Up[B][c].size() - 1;i >= 0;i--){
int T = Up[B][c][i];
if(verify(T,B,L,R)) ans++;
else break;
}
}
}
}
return ans;
}
