#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int,int> ii;
static int Left[2505][2505]; ///Left[r][c]: Left boundary from (r,c) provided (r,c) < (Left[r][c],c)
static 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
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++){
vector<ii> s; s.push_back(ii(1e9,-1));
//cout << r << ": \n";
for(int i = 0;i < cols;i++){
while(true){
ii back = s.back();
if(back.second != -1 && back.second != i - 1){
//cout << s.back().second << " " << i << " " << "\n";
int L = s.back().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.back().first >= arr[r][i]){
if(s.back().first == arr[r][i]) s.pop_back();
break;
}
s.pop_back();
}
s.push_back(ii(arr[r][i],i));
}
}
for(int c = 0;c < cols;c++){
vector<ii> s; s.push_back(ii(1e9,-1));
//cout << c << ": \n";
for(int i = 0;i < rows;i++){
while(true){
ii back = s.back();
if(back.second != -1 && back.second != i - 1){
//cout << s.back().second << " " << i << " " << "\n";
int T = s.back().second;
int B = i;
UpDown[T][B].push_back(c);
Up[B][c].push_back(T);
//cout << B << " " << c << " " << T << "\n";
}
if(s.back().first >= arr[i][c]){
if(s.back().first == arr[i][c]) s.pop_back();
break;
}
s.pop_back();
}
s.push_back(ii(arr[i][c],i));
}
}
int ans = 0;
for(int r = 1;r < rows - 1;r++){
for(int c = 1;c < cols;c++){
if(Right[r][c-1] != -1){
int B = r + 1;
int L = c - 1;
int R = Right[r][L];
for(int T : Up[B][c]){
//cout << T << " " << B << " " << L << " " << R << " ";
//cout << verify(T,B,L,R) << "\n";
ans += verify(T,B,L,R);
}
}
if(Left[r][c+1] != -1){
//cout << r << " " << c << " " << "BR\n";
int B = r + 1;
int R = c + 1;
int L = Left[r][R];
for(int T : Up[B][c]){
//cout << T << " " << B << " " << L << " " << R << " ";
//cout << verify(T,B,L,R) << "\n";
ans += verify(T,B,L,R);
}
}
}
}
return ans;
}
