#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll count_rectangles(vector<vector<int>> a) {
ll ans = 0;
int n = a.size();
int m = a[0].size();
if (n <= 2 or m <= 2) {
return 0;
}
int mx[n][m][m], mx2[m][n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
mx[i][j][j] = a[i][j];
for (int k = j+1; k < m; ++k) {
mx[i][j][k] = max(mx[i][j][k-1], a[i][k]);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mx2[i][j][j] = a[j][i];
for (int k = j+1; k < n; ++k) {
mx2[i][j][k] = max(mx2[i][j][k-1], a[k-1][i]);
}
}
}
//mn mx stores min max for all rows
//mn2 stores min for all columns
vector<array<int, 4>> vec;
for (int i = 1; i < n-1; ++i) {
for (int j = 1; j < m-1; ++j) {
pair<int, int> top_right{i, j};
for (int k = i; k < n-1; ++k) {
for (int l = j; l < n-1; ++l) {
pair<int, int> bottom_left{k, l};
/*int mini = 1e9;
int maxi = 0;
for (int row = top_right.first; row <= bottom_left.first; ++row) {
maxi = max(maxi, mx[row][top_right.second][bottom_left.second]);
}
mini = min(mini, mn[top_right.first-1][top_right.second][bottom_left.second]);
mini = min(mini, mn[bottom_left.first+1][top_right.second][bottom_left.second]);
mini = min(mini, mn2[top_right.second-1][top_right.first][bottom_left.first]);
mini = min(mini, mn2[bottom_left.second+1][top_right.first][bottom_left.first]);
if (i == 4 and j == 2 and k == 4 and l == 3) {
cerr << "during 4 2 4 3 : \nmini = " << mini << " maxi = " << maxi << '\n';
}
if (maxi <= mini) {
vec.push_back({i, j, k, l, mini, maxi});
}*/
bool cont = false;
for (int row = top_right.first; row <= bottom_left.first; ++row) {
int maxi = mx[row][top_right.second][bottom_left.second];
if (maxi > min(a[row][top_right.second-1], a[row][bottom_left.second+1])) {
cont = true;
break;
}
}
if (cont) continue;
for (int col = top_right.second; col <= bottom_left.second; ++col) {
int maxi = mx2[col][top_right.first][bottom_left.first];
if (maxi > min(a[top_right.first-1][col], a[bottom_left.first+1][col])) {
cont = true;
break;
}
}
if (cont) continue;
ans++;
vec.push_back({i, j, k, l});
}
}
}
}
/*for (auto x : vec) {
for (auto y : x) cout << y << " " ;
cout << '\n';
}*/
return ans;
}
/*
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m));
for (auto &x : v) for (auto &y : x) cin >> y;
cout << count_rectangles(v);
}
*/
