#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
long long count_rectangles(std::vector<std::vector<int> > vec) {
int n=sz(vec);
int m=sz(vec[0]);
const int MOD=1e9+7;
vector<vector<int>> up(n,vector<int> (m,-1));
vector<vector<int>> dwn(n,vector<int> (m,MOD));//mod
L(j,1,m-2){
//olhando pra fila j
vector<int> fila;
L(i,0,n-1){
while(!fila.empty() && vec[fila.back()][j]<vec[i][j]){
dwn[fila.back()][j]=i;
fila.pop_back();
}
if(!fila.empty()){
up[i][j]=fila.back();
}
fila.push_back(i);
}
}
vector<vector<int>> lef(n,vector<int> (m,-1));
vector<vector<int>> rig(n,vector<int> (m,MOD));//mod
L(i,1,n-2){
vector<int> fila;
L(j,0,m-1){
while(!fila.empty() && vec[i][fila.back()]<vec[i][j]){
rig[i][fila.back()]=j;
fila.pop_back();
}
if(!fila.empty()){
lef[i][j]=fila.back();
}
fila.push_back(j);
}
}
/*
L(i,0,n-1){
L(j,0,m-1){
cout<<rig[i][j]<<" ";
}
cout<<"\n";
}
*/
int resp=0;
L(a,1,n-2){
L(b,a,n-2){
L(c,1,m-2){
L(d,c,m-2){
int ok=1;
L(i,a,b){
L(j,c,d){
if(up[i][j]<a-1 || dwn[i][j]>b+1 || lef[i][j]<c-1 || rig[i][j]>d+1)ok=0;
}
}
resp+=ok;
}
}
}
}
return resp;
}
