#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;
const ll MAXN = 2e5+5;
const ll INF = 1e9+7;
long long count_rectangles(std::vector<std::vector<int> > a) {
ll n=a.size(),m=a[0].size(),i,j,ii,jj,A,B,ans=0;
bool ok;
int nearest[n+1][m+1][4];
stack<int>s;
for(i=0;i<n;i++){//left
while(!s.empty())s.pop();
for(j=m-1;j>=0;j--){
while(!s.empty() && a[i][s.top()]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][0]=m;
}else{
nearest[i][j][0]=s.top();
}
s.push(j);
}
}
for(i=0;i<n;i++){//right
while(!s.empty())s.pop();
for(j=0;j<m;j++){
while(!s.empty() && a[i][s.top()]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][1]=-1;
}else{
nearest[i][j][1]=s.top();
}
s.push(j);
}
}
for(j=0;j<m;j++){//down
while(!s.empty())s.pop();
for(i=n-1;i>=0;i--){
while(!s.empty() && a[s.top()][j]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][2]=n;
}else{
nearest[i][j][2]=s.top();
}
s.push(i);
}
}
for(j=0;j<m;j++){//up
while(!s.empty())s.pop();
for(i=0;i<n;i++){
while(!s.empty() && a[s.top()][j]<a[i][j]){
s.pop();
}
if(s.empty()){
nearest[i][j][3]=-1;
}else{
nearest[i][j][3]=s.top();
}
s.push(i);
}
}
/*
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cout<<nearest[i][j][0]<<" ";
}cout<<endl;
}cout<<endl;*/
for(i=1;i<n-1;i++){
for(j=1;j<m-1;j++){
for(ii=i;ii<n-1;ii++){
for(jj=j;jj<m-1;jj++){
ok=true;
for(A=i;A<=ii;A++){//verificar esta
if(nearest[A][j-1][0]<=jj || nearest[A][jj+1][1]>=j ){
ok=false;
break;
}
}
if(!ok)continue;
for(B=j;B<=jj;B++){//verificar esta
if(nearest[i-1][B][2]<=ii || nearest[ii+1][B][3]>=i){
ok=false;
break;
}
}
if(ok)ans++;
}
}
}
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
return ans;
}
