#include "rect.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mp make_pair
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ll = long long;
ll count_rectangles(vector<vector<int> > a) {
ll ans = 0;
int n = (int)a.size(), m = (int)a[0].size();
vector<vector<vector<ii> > > horiz(n, vector<vector<ii> >(m)), vert(n, vector<vector<ii> >(m));
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
for (int k = j, r = 0; k >= 1; k--) {
r = max(r, a[i][k]);
if (r < min(a[i][j + 1], a[i][k - 1])) horiz[i][j].eb(k, 1);
}
}
}
for (int j = 1; j + 1 < m; j++) {
for (int i = 1; i + 1 < n; i++) {
for (int k = i, r = 0; k >= 1; k--) {
r = max(r, a[k][j]);
if (r < min(a[i + 1][j], a[k - 1][j])) vert[i][j].eb(k, 1);
}
}
}
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
reverse(horiz[i][j].begin(), horiz[i][j].end());
reverse(vert[i][j].begin(), vert[i][j].end());
for (auto &[k, l] : horiz[i][j]) {
auto it = lower_bound(horiz[i - 1][j].begin(), horiz[i - 1][j].end(), mp(k, 0));
if (it != horiz[i - 1][j].end() && it->first == k) {
l = it->second + 1;
}
}
for (auto &[k, l] : vert[i][j]) {
auto it = lower_bound(vert[i][j - 1].begin(), vert[i][j - 1].end(), mp(k, 0));
if (it != vert[i][j - 1].end() && it->first == k) {
l = it->second + 1;
}
}
vector<iii> events;
for (auto [k1, l1] : horiz[i][j]) {
events.eb(j - k1 + 1, 0, l1);
}
for (auto [k2, l2] : vert[i][j]) {
events.eb(l2, 1, i - k2 + 1);
}
sort(events.begin(), events.end());
tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ss;
int idx = 0;
for (auto [_, type, x] : events) {
if (type == 0) {
ss.insert(mp(x, idx++));
} else {
ans += (int)ss.size() - ss.order_of_key(mp(x, -1));
}
}
}
}
return ans;
}
