#include <bits/stdc++.h>
#include "rect.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
ll count_rectangles(Vec<Vec<int>> a) {
const int n = (int) a.size();
const int m = (int) a[0].size();
Vec<Vec<std::pair<int, int>>> cand(n);
for (int i = 0; i < n; ++i) {
Vec<int> stack;
for (int j = 0; j < m; ++j) {
while (!stack.empty() and a[i][stack.back()] < a[i][j]) {
if (stack.back() + 1 < j) {
cand[i].emplace_back(stack.back(), j);
}
stack.pop_back();
}
if (!stack.empty() and stack.back() + 1 < j) {
cand[i].emplace_back(stack.back(), j);
}
stack.push_back(j);
}
std::sort(cand[i].begin(), cand[i].end());
}
ll ret = 0;
for (int u = 0; u < n; ++u) {
Vec<int> max(m);
Vec<int> ok(m + 1);
Vec<std::pair<int, int>> pair;
for (int d = u + 2; d < n; ++d) {
for (int j = 0; j < m; ++j) {
max[j] = std::max(max[j], a[d - 1][j]);
ok[j + 1] = ok[j] + (max[j] < std::min(a[u][j], a[d][j]));
}
if (d == u + 2) {
pair = cand[d - 1];
} else {
Vec<std::pair<int, int>> next;
const auto& add = cand[d - 1];
int l = 0, r = 0;
while (l < (int) pair.size() and r < (int) add.size()) {
if (pair[l] < add[r]) {
l += 1;
} else if (add[r] < pair[l]) {
r += 1;
} else {
next.emplace_back(pair[l]);
l += 1;
r += 1;
}
}
pair = std::move(next);
}
for (const auto [l, r]: pair) {
if (ok[r] - ok[l + 1] == r - (l + 1)) {
// std::cerr << u << ' ' << d << ' ' << l << ' ' << r << std::endl;
ret += 1;
}
}
}
}
return ret;
}
