#include "rect.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int (s.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
ll n,m;
ll mxf[210][210][210], mxc[210][210][210];
vector< vector<int> > A;
void loco(vector<int> s, int x){//filas
for(int i=1; i<m-1; i++){
int mx=s[i];
for(int j=i; j<m-1; j++){
mx=max(mx,s[j]);
mxf[x][i][j]=mx;
}
}
return;
}
void loca(vector<int> s, int x){//columnas
for(int i=1; i<n-1; i++){
int mx=s[i];
for(int j=i; j<n-1; j++){
mx=max(mx,s[j]);
mxc[x][i][j]=mx;
}
}
return;
}
bool validf(int mx, int i, int l, int r){
return A[i][l-1]>mx && A[i][r+1]>mx;
}
bool validc(int mx, int j, int l, int r){
return A[l-1][j]>mx && A[r+1][j]>mx;
}
bool rectangle(int a, int b, int x, int y){
bool good=true;
for(int i=a; i<=x; i++){//por filas
good&=validf(mxf[i][b][y], i, b, y);
}
for(int j=b; j<=y; j++){//por columnas
good&=validc(mxc[j][a][x], j, a, x);
}
return good;
}
int fijo(int i1, int j1){
int ans=0;
for(int i=i1; i<n-1; i++){
for(int j=j1; j<m-1; j++){
if(rectangle(i1, j1, i, j)) ans++;
}
}
return ans;
}
ll tmx(int k){
int mx=0, ans=0;
for(int i=k; i<m-1; i++){
mx=max(mx,A[1][i]);
if(A[1][i]<A[0][i] && A[1][i]<A[2][i]){
if(mx<A[1][k-1] && mx<A[1][i+1])ans++;
}
else break;
}
return ans;
}
long long count_rectangles(vector< vector<int> > a) {
A=a;
n=sz(a);
m=sz(a[0]);
int ans=0;
if(n<3)return ans;
if(n==3){
for(int i=1; i<m-1; i++){
ans+=tmx(i);
//cout<<i<<':'<<tmx(i)<<'\n';
}
//cout<<ans<<'\n';
return ans;
}
for(int i=0; i<n; i++){
loco(a[i], i);
}
vector<int> c;
for(int j=0; j<m; j++){
for(int i=0; i<n; i++){
c.pb(a[i][j]);
}
loca(c,j);
c.clear();
}
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
ans+=fijo(i,j);
}
}
return 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
3 10
1 2 4 5 6 3 6 7 4 8
8 1 9 2 1 1 1 1 1 9
9 7 5 7 5 9 9 4 3 8
1 1
1 1 2 1
1
1 1 1
1 1 2 1 6 1 1 1
*/
