#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int,int> ii;
struct query{ int id; int L; int R; int type; };
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 int LeftRightPtr[2505][2505];
static int UpDownPtr[2505][2505];
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
static vector<query> LeftRightQuery[2505];
static vector<query> UpDownQuery[2505];
static vector<ii> rects;
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++){
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){
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));
for(int i = 0;i < rows;i++){
while(true){
ii back = s.back();
if(back.second != -1 && back.second != i - 1){
int T = s.back().second;
int B = i;
UpDown[T][B].push_back(c);
Up[B][c].push_back(T);
}
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 rectNo = 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 T : Up[B][c]){
//cout << T << " " << B << " " << L << " " << R << " " << verify(T,B,L,R) << "\n";
rects.push_back(ii(R-L-1, B-T-1));
LeftRightQuery[T].push_back({rectNo, L, R, -1});
LeftRightQuery[B-1].push_back({rectNo, L, R, 1});
UpDownQuery[L].push_back({rectNo, T, B, -1});
UpDownQuery[R-1].push_back({rectNo, T, B, 1});
rectNo++;
}
}
if(Left[r][c+1] != -1){
int B = r + 1;
int R = c + 1;
int L = Left[r][R];
for(int T : Up[B][c]){
//cout << T << " " << B << " " << L << " " << R << " " << verify(T,B,L,R) << "\n";
rects.push_back(ii(R-L-1, B-T-1));
LeftRightQuery[T].push_back({rectNo, L, R, -1});
LeftRightQuery[B-1].push_back({rectNo, L, R, 1});
UpDownQuery[L].push_back({rectNo, T, B, -1});
UpDownQuery[R-1].push_back({rectNo, T, B, 1});
rectNo++;
}
}
}
}
//cout << "\n";
///The reason why I need to do this is cause O(N^2logN) somehow doesn't pass .-.
for(int r = 0;r < rows;r++){
for(query q : LeftRightQuery[r]){
int L = q.L, R = q.R;
while(LeftRightPtr[L][R] < (int) LeftRight[L][R].size()){
if(LeftRight[L][R][LeftRightPtr[L][R]] > r) break;
LeftRightPtr[L][R]++;
}
//cout << r << " " << q.id << " " << q.type << " " << LeftRightPtr[L][R] << "\n";
rects[q.id].second -= q.type * LeftRightPtr[L][R];
}
}
for(int c = 0;c < cols;c++){
for(query q : UpDownQuery[c]){
int T = q.L, B = q.R;
while(UpDownPtr[T][B] < (int) UpDown[T][B].size()){
if(UpDown[T][B][UpDownPtr[T][B]] > c) break;
UpDownPtr[T][B]++;
}
rects[q.id].first -= q.type * UpDownPtr[T][B];
}
}
int ans = 0;
for(ii Rect : rects){
//cout << Rect.first << " " << Rect.second << "\n";
if(Rect.first == 0 && Rect.second == 0) ans++;
}
return ans;
}
