#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 710;
bitset<MAXN> lVal[MAXN][MAXN];
bitset<MAXN> cVal[MAXN][MAXN];
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
for(int i = 1; i < n - 1; i++){
for(int j = 1; j < m - 1; j++){
int maxi = 0;
for(int k = j; k < m - 1; k++){
maxi = max(maxi, a[i][k]);
lVal[i][j][k] = maxi < a[i][j - 1] && maxi < a[i][k + 1];
}
}
}
for(int i = 1; i < m - 1; i++){
for(int j = 1; j < n - 1; j++){
int maxi = 0;
for(int k = j; k < n - 1; k++){
maxi = max(maxi, a[k][i]);
cVal[i][j][k] = maxi < a[j - 1][i] && maxi < a[k + 1][i];
}
}
}
long long ans = 0;
for(int i = 1; i < n - 1; i++){
for(int j = 1; j < m - 1; j++){
bitset<MAXN> marc = lVal[i][j];
for(int k = i; k < n - 1; k++){
marc &= lVal[k][j];
for(int l = j; l < m - 1; l++){
if(cVal[l][i][k] == 0) break;
ans += marc[l];
}
}
}
}
return ans;
}
