#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long count_rectangles(vector<vector<int> > a) {
int N = a.size(),M = a[0].size();
if(N < 3 || M < 3) return 0LL;
vector<vector<vector<short>>> horivalid(N,vector<vector<short>>(M,vector<short>(M,0)));// i,l,r
vector<vector<vector<short>>> vertvalid(M,vector<vector<short>>(N,vector<short>(N,0)));// j,l,r;
for(int i = 0;i < N;i++){
for(int l = 0;l+2 < M;l++){
int cmax = a[i][l+1];
for(int r = l+2;r < M;r++){
if(cmax < a[i][l] && cmax < a[i][r]){
horivalid[i][l][r] = true;
}
cmax = max(cmax,a[i][r]);
if(a[i][l] <= cmax) break;
}
}
}
for(int j = 0;j < M;j++){
for(int l = 0;l+2 < N;l++){
int cmax = a[l+1][j];
for(int r = l+2;r < N;r++){
if(cmax < a[l][j] && cmax < a[r][j]){
vertvalid[j][l][r] = true;
}
cmax = max(cmax,a[r][j]);
if(a[l][j] <= cmax) break;
}
}
}
for(int i = 1;i < N;i++){
for(int l = 0;l < M;l++){
for(int r = 0;r < M;r++){
if(horivalid[i][l][r]){
horivalid[i][l][r] += horivalid[i-1][l][r];
}
}
}
}
for(int j = 1;j < M;j++){
for(int l = 0;l < N;l++){
for(int r = 0;r < N;r++){
if(vertvalid[j][l][r]){
vertvalid[j][l][r] += vertvalid[j-1][l][r];
}
}
}
}
long long ans = 0;
for(int bottom = 1;bottom+1 < N;bottom++){
for(int l = 0;l+2 < M;l++){
for(int r = l+2;r < M;r++){
int minTop = max(0,bottom-horivalid[bottom][l][r]);
int cbottom = bottom+1;
for(int ctop = minTop;ctop < bottom;ctop++){
// cout << l+1 << " " << r-1 << " " << ctop+1 << " " << cbottom-1 << endl;
if(vertvalid[r-1][ctop][cbottom] >= r-l-1) ans++;
}
}
}
}
return ans;
}
