#include <cstring>
#pragma GCC optimize("Ofast,unroll-loops")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
bool cols[699][699][699];
short int upw[699][699][699];
long long count_rectangles(vector<vector<int>> a) {
memset(cols, 0, sizeof cols);
memset(upw, 0, sizeof upw);
int n=a.size(), m=a[0].size();
int cmx, j, up, down, i, l, r;
for (i=1; i<n-1; i++){
for (l=1; l<m-1; l++){
cmx=a[i][l];
for (r=l; r<m-1; r++){
cmx=max(cmx, a[i][r]);
if (cmx<a[i][l-1] and cmx<a[i][r+1]){
cols[i][l][r]=1;
}
}
}
}
for (i=1; i<n-1; i++){
for (l=1; l<m-1; l++){
for (r=l; r<m-1; r++){
upw[i][l][r]=(cols[i][l][r]?upw[i-1][l][r]+1:0);
}
}
}
for (j=1; j<m-1; j++){
for (up=1; up<n-1; up++){
cmx=a[up][j];
for (down=up; down<n-1; down++){
cmx=max(cmx, a[down][j]);
if (cmx<a[up-1][j] and cmx<a[down+1][j]){
cols[j][up][down]=1;
}else cols[j][up][down]=0;
}
}
}
long long cnt=0;
for (up=1; up<n-1; up++){
for (down=up; down<n-1; down++){
for (r=1; r<m-1; r++){
for (l=r; l>=1; l--){
if (!cols[l][up][down]){
break;
}
if (upw[down][l][r]>=(down-up+1)) {
cnt++;
}
}
}
}
}
return cnt;
}
