#include <bits/stdc++.h>
#include "rect.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
ll count_rectangles(vector<vector<int>> a) {
int n = (int)a.size(), m = (int)a[0].size();
vector<vector<int>> L(n, vector<int>(m)), R = L, U = L, D = L;
for (int i = 0; i < n; i++) {
stack<int> s;
for (int j = 0; j < m; j++) {
while (!s.empty() && a[i][s.top()] < a[i][j]) s.pop();
L[i][j] = (s.empty() ? 0 : s.top());
s.push(j);
}
while (!s.empty()) s.pop();
for (int j = m - 1; j >= 0; j--) {
while (!s.empty() && a[i][j] > a[i][s.top()]) s.pop();
R[i][j] = (s.empty() ? m - 1 : s.top());
s.push(j);
}
}
for (int i = 0; i < m; i++) {
stack<int> s;
for (int j = 0; j < n; j++) {
while (!s.empty() && a[s.top()][i] < a[j][i]) s.pop();
U[j][i] = (s.empty() ? 0 : s.top());
s.push(j);
}
while(!s.empty()) s.pop();
for (int j = n - 1; j >= 0; j--) {
while (!s.empty() && a[j][i] > a[s.top()][i]) s.pop();
D[j][i] = (s.empty() ? n - 1 : s.top());
s.push(j);
}
}
int cnt = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
int mn = INT_MAX;
for (int k = i; k < D[i - 1][j] && j < R[k][j - 1]; k++) {
mn = min(mn, R[k][j - 1]);
for (int l = j; l < mn && k < D[i - 1][l] && U[k + 1][l] < i; l++) {
bool tr = true;
for (int m = i; m <= k && tr; m++)
tr = (L[m][l + 1] < j);
cnt += tr;
}
}
}
}
return cnt;
}
