#include "rect.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 7e6 + 5;
int bit[mxN];
void upd(int i, int v) {
for (; i < mxN; i += i & (-i)) bit[i] += v;
}
int sum(int i) {
int ret = 0;
for (; i > 0; i -= i & (-i)) ret += bit[i];
return ret;
}
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
if (n <= 2 || m <= 2) return 0;
long long ans = 0;
bool good[n][n][m];
memset(good, 0, sizeof good);
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
int mx = 0;
for (int ii = i; ii < n - 1; ii++) {
mx = (i == ii ? a[i][j] : max(a[ii][j], mx));
good[i][ii][j] = (mx < min(a[i - 1][j], a[ii + 1][j]));
}
}
}
bool gg[m][m][n];
memset(gg, 0, sizeof gg);
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
int mx = 0;
for (int ii = i; ii < m - 1; ii++) {
mx = (i == ii ? a[j][i] : max(a[j][ii], mx));
gg[i][ii][j] = (mx < min(a[j][i - 1], a[j][ii + 1]));
}
}
}
int tor[n][n][m];
memset(tor, -1, sizeof tor);
for (int i = 1; i < n - 1; i++) {
for (int ii = i; ii < n - 1; ii++) {
for (int j = m - 2; j >= 1; j--) {
if (good[i][ii][j]) tor[i][ii][j] = j;
if (good[i][ii][j]) tor[i][ii][j] = max(tor[i][ii][j], tor[i][ii][j + 1]);
}
}
}
int toc[m][m][n];
memset(toc, -1, sizeof toc);
for (int i = 1; i < m - 1; i++) {
for (int ii = i; ii < m - 1; ii++) {
for (int j = n - 2; j >= 1; j--) {
if (gg[i][ii][j]) toc[i][ii][j] = j;
if (gg[i][ii][j]) toc[i][ii][j] = max(toc[i][ii][j], toc[i][ii][j + 1]);
}
}
}
int total = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
vector<pair<int, int>> a, b;
for (int ii = i; ii < n - 1; ii++) {
if (tor[i][ii][j] != -1) a.push_back({ii, tor[i][ii][j]});
}
for (int ii = j; ii < m - 1; ii++) {
if (toc[j][ii][i] != -1) b.push_back({toc[j][ii][i], ii});
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int p1 = 0;
int sa = a.size(), sb = b.size();
total = 0;
for (int cur = 0; cur < sb; cur++) {
while (p1 < sa && a[p1].first <= b[cur].first) {
upd(a[p1++].second, 1);
total++;
}
ans += total - sum(b[cur].second - 1);
}
for (int cur = 0; cur < p1; cur++) upd(a[cur].second, -1);
}
}
return ans;
}
