#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 700;
short pref2[N][N][N];
vector<vector<vector<bool>>> pref1(N, vector<vector<bool>>(N, vector<bool>(N)));
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
// vector<basic_string<vector<short>>> pref1(m, vector<vector<short>>(n, vector<short>(n)));
for (int l = 0; l + 1 < n; l++) {
for (int j = 1; j + 1 < m; j++) {
int mx = a[l + 1][j];
for (int r = l + 2; r < n; r++) {
pref1[j][l][r] = (min(a[l][j], a[r][j]) > mx);
mx = max(mx, a[r][j]);
}
}
}
// vector<basic_string<vector<short>>> pref2(n, vector<vector<short>>(m, vector<short>(m)));
for (int l = 0; l + 1 < m; l++) {
for (int i = 1; i + 1 < n; i++) {
int mx = a[i][l + 1];
for (int r = l + 2; r < m; r++) {
pref2[i][l][r] = pref2[i - 1][l][r] + (min(a[i][l], a[i][r]) > mx);
mx = max(mx, a[i][r]);
}
}
}
ll ans = 0;
for (int l1 = 0; l1 < n; l1++) {
for (int r1 = l1 + 2; r1 < n; r1++) {
for (int l2 = 0; l2 < m; l2++) {
for (int r2 = l2 + 2; r2 < m; r2++) {
if (!pref1[r2 - 1][l1][r1]) break;
ans += pref2[r1 - 1][l2][r2] - pref2[l1][l2][r2] == r1 - l1 - 1;
}
}
}
}
return ans;
}
