#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> b[2505][2505];
vector<vector<int>> aa;
int f(int i,int j,int x,int y){
int cnt1 = 0;
int cnt2 = 0;
for(int k=i ; k<=j ; k++){
if(aa[x][k]<aa[y][k])
cnt1++;
if(aa[x][k]>aa[y][k])
cnt2++;
}
if(cnt1==j-i+1)return 1;
if(cnt2==j-i+1)return -1;
return 0;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
aa=a;
int n = a.size();
int m = a[0].size();
for(int i=1 ; i<n-1 ; i++){
stack<int> S;
for(int j=0 ; j<m ; j++){
bool flag = true;
while(!S.empty() && a[i][S.top()] <= a[i][j]){
int x = S.top();
if(x +1 <j && flag)
b[x+1][j-1].push_back(i);
if(a[i][S.top()]==a[i][j])flag=false;
S.pop();
}
if(!S.empty() && flag){
int x = S.top();
if(x+1<j)
b[x+1][j-1].push_back(i);
}
S.push(j);
}
}
long long ans = 0;
for(int i=1 ; i<m ; i++){
for(int j=i ; j<m ; j++){
vector<vector<int>> c;
int prv=-1;
for(int x: b[i][j]){
// cout<<i<<" "<<j<<" "<<x<<endl;
if(prv+1<x)
c.push_back({x});
else
c.back().push_back(x);
prv=x;
}
for(auto d: c){
stack<int> S;
d.push_back(d.back()+1);
d.push_back(d[0]-1);
sort(d.begin(),d.end());
for(auto x: d){
bool flag = true;
while(!S.empty() && f(i,j,S.top(),x)>=0){
int k = S.top(); S.pop();
if(k +1 <x && flag){
ans++;
}
if(f(i,j,k,x)==0){
flag=false;
}
}
if(!S.empty() && S.top()+1<x && flag){
bool flag = true;
for(int l = S.top()+1 ; l<x ; l++)
if(f(i,j,l,x)<=0)flag = false;
ans+=flag;
}
S.push(x);
}
}
}
}
return ans;
}
