#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>> left(n + 1, vector<int>(m + 1));
vector<vector<int>> right(n + 1, vector<int>(m + 1));
vector<vector<int>> top(n + 1, vector<int>(m + 1));
vector<vector<int>> bot(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
left[i + 1][j + 1] = left[i + 1][j] + left[i][j + 1] - left[i][j] + (a[i][j] >= a[i][j - 1]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
right[i + 1][j + 1] = right[i + 1][j] + right[i][j + 1] - right[i][j] + (a[i][j] >= a[i][j + 1]);
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
bot[i + 1][j + 1] = bot[i + 1][j] + bot[i][j + 1] - bot[i][j] + (a[i][j] >= a[i + 1][j]);
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
top[i + 1][j + 1] = top[i + 1][j] + top[i][j + 1] - top[i][j] + (a[i][j] >= a[i - 1][j]);
}
}
auto get = [&](vector<vector<int>> &p, 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(left, r1, c1, r2, c1) != 0) continue;
if (a[r1][c1] >= a[r1 - 1][c1]) continue;
if (a[r2][c1] >= a[r2 + 1][c1]) continue;
int l = c1, r = m - 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (get(top, r1, c1, r1, mid) == 0 && get(bot, r1, c1, r1, mid) == 0) {
l = mid;
} else {
r = mid;
}
}
for (int c2 = c1; c2 <= l; 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;
}
