#include <bits/stdc++.h>
//#include "rect.h"
using namespace std;
const int MN = 701;
bool canV[MN][MN][MN], canH[MN][MN][MN];
long long count_rectangles (vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<vector<bool>>> canV(m,vector<vector<bool>>(n,vector<bool>(n)));
vector<vector<vector<bool>>> canH(n,vector<vector<bool>>(m,vector<bool>(m)));
vector<vector<vector<int>>> psaV(n,vector<vector<int>>(n,vector<int>(m)));
vector<vector<vector<int>>> psaH(m,vector<vector<int>>(m,vector<int>(n)));
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
int mx = a[i][j];
for (int k = j; k + 1 < m; k++) {
mx = max(mx,a[i][k]);
canH[i][j][k] = a[i][j-1] > mx && a[i][k+1] > mx;
}
}
}
for (int j = 1; j + 1 < m; j++) {
for (int k = j; k + 1 < m; k++) {
for (int i = 1; i + 1 < n; i++) {
psaH[j][k][i] = psaH[j][k][i-1] + !canH[i][j][k];
}
}
}
for (int i = 1; i + 1 < m; i++) {
for (int j = 1; j + 1 < n; j++) {
int mx = a[j][i];
for (int k = j; k + 1 < n; k++) {
mx = max(mx,a[k][i]);
canV[i][j][k] = a[j-1][i] > mx && a[k+1][i] > mx;
}
}
}
for (int j = 1; j + 1 < n; j++) {
for (int k = j; k + 1 < n; k++) {
for (int i = 1; i + 1 < m; i++) {
psaV[j][k][i] = psaV[j][k][i-1] + !canV[i][j][k];
}
}
}
long long ans = 0;
for (int i = 1; i + 1 < n; i++) {
for (int j = i; j + 1 < n; j++) { //rows[i --> j]
for (int k = 1; k + 1 < m; k++) {
for (int l = k; l + 1 < m; l++) { //cols[k --> l]
ans += psaV[i][j][l] == psaV[i][j][k-1] && psaH[k][l][j] == psaH[k][l][i-1];
}
}
}
}
return ans;
}
//int main () {
// printf ("%lld\n",count_rectangles({{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}}));
// return 0;
//}
