#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin() + 1, (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
template<typename T>void debug_var(const T& var, const string& name){
cerr << name << ": " << var << "\n";
}
template<typename T>void debug_1d(const T& vt, const string& name){
if(vt.empty()){
cerr << name << " is empty!\n";
return;
}
FOR(i, 0, (int)vt.size() - 1){
cerr << name << "[" << i << "]: " << vt[i] << "\n";
}
}
ll sub2(const vector<vector<int>>& a){
int n = a.size(), m = a[0].size();
ll ans = 0;
if(n < 3 || m < 3) return 0;
FOR(r1, 1, n - 2){
FOR(r2, r1, n - 2){
int row = r2 - r1 + 1;
vector<int> ds_max(m);
FOR(j, 0, m - 1){
FOR(i, r1, r2) ds_max[j] = max(ds_max[j], a[i][j]);
}
//debug_1d(ds_max, "row max");
FOR(c1, 1, m - 2){
vector<int> row_max(row, -1e9);
FOR(c2, c1, m - 2){
FOR(i, r1, r2){
if(a[i][c2] > row_max[i - r1]) row_max[i - r1] = a[i][c2];
}
int right = a[r1 - 1][c2] < a[r2 + 1][c2] ? a[r1 - 1][c2] : a[r2 + 1][c2];
if(!(ds_max[c2] < right)) break;
bool ok = true;
FOR(i, r1, r2){
int lim = a[i][c1 - 1] < a[i][c2 + 1] ? a[i][c1 - 1] : a[i][c2 + 1];
if(!(row_max[i - r1] < lim)){
ok = false;
break;
}
}
if(ok) ++ans;
}
}
}
}
return ans;
}
ll count_rectangles(vector<vector<int>> a){
return sub2(a);
}
/*
void solve(){
vector<vector<int>> grid = {
{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}
};
cout << count_rectangles(grid);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
*/
