#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N,M;
vector<vector<int>> row,col,arr;
ll calc(int sr,int sc){
//cerr<<sr<<','<<sc<<endl;
for(int i = 0;i<N;i++)for(int j = 0;j<M;j++)col[i][j] = row[i][j] = 0;
ll re = 0;
for(int i = 0;i<N;i++)row[i][sc] = col[i][sc] = -1;
for(int i = 0;i<M;i++)col[sr][i] = row[sr][i] = -1;
for(int i = sr+1;i+1<N;i++){
for(int j = sc+1;j+1<M;j++){
row[i][j] = max(row[i][j-1],arr[i][j]);
col[i][j] = max(col[i-1][j],arr[i][j]);
}
}
/*
cerr<<sr+1<<' '<<sc+1<<":"<<endl;
for(int i = sr;i+1<N;i++){
for(int j = sc;j+1<M;j++)cerr<<row[i][j];cerr<<endl;
}cerr<<endl;
for(int i = sr;i+1<N;i++){
for(int j = sc;j+1<M;j++)cerr<<col[i][j];cerr<<endl;
}
*/
for(int i = sr+1;i+1<N;i++){
for(int j = sc+1;j+1<M;j++){
if(!row[i-1][j]||row[i][j]>=min(arr[i][sc],arr[i][j+1]))row[i][j] = 0;
else row[i][j] = -1;
if(!col[i][j-1]||col[i][j]>=min(arr[sr][j],arr[i+1][j]))col[i][j] = 0;
else col[i][j] =- 1;
if(row[i][j] == -1&&col[i][j] == -1){
//cerr<<"FOUND: "<<sr+1<<' '<<sc+1<<' '<<i<<' '<<j<<endl;
re++;
}
}
}
/*
cerr<<sr+1<<' '<<sc+1<<":"<<endl;
for(int i = sr;i+1<N;i++){
for(int j = sc;j+1<M;j++)cerr<<row[i][j];cerr<<endl;
}cerr<<endl;
for(int i = sr;i+1<N;i++){
for(int j = sc;j+1<M;j++)cerr<<col[i][j];cerr<<endl;
}
*/
return re;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
N = a.size(),M = a[0].size();
row = col = vector<vector<int>>(N,vector<int>(M,0));
arr = a;
ll ans = 0;
for(int i = 0;i+1<N;i++){
for(int j = 0;j+1<M;j++){
ans += calc(i,j);
}
}
return ans;
}
