#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<vector<int>> p(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
p[i + 1][j + 1] = p[i + 1][j] + p[i][j + 1] - p[i][j] + (a[i][j] > a[i][j - 1]);
}
}
auto get = [&](int x1, int y1, int x2, int y2) {
x1++; y1++; x2++; y2++;
return p[x2][y2] - p[x2][y1 - 1] - p[x1 - 1][y2] + p[x1 - 1][y1 - 1];
};
long long ans = 0;
for (int r1 = 1; r1 < n - 1; r1++) {
for (int r2 = r1; r2 < n - 1; r2++) {
for (int c1 = 1; c1 < m - 1; c1++) {
if (get(r1, c1, r2, c1) != 0) continue;
for (int c2 = c1; c2 < m - 1; c2++) {
bool ok = true;
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
int x = min({a[i][c1 - 1], a[i][c2 + 1], a[r1 - 1][j], a[r2 + 1][j]});
if (a[i][j] >= x) {
ok = false;
break;
}
}
if (!ok) {
break;
}
}
ans += ok;
}
}
}
}
return ans;
}
