#include <bits/stdc++.h>
#include "rect.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
struct Fenwick {
Vec<int> data;
explicit Fenwick(const int n): data(n + 1) {}
void add(int i, const int x) {
i += 1;
while (i < (int) data.size()) {
data[i] += x;
i += i & -i;
}
}
int get(int i) const {
int x = 0;
while (i > 0) {
x += data[i];
i -= i & -i;
}
return x;
}
int fold(const int l, const int r) const {
return get(r) - get(l);
}
};
ll count_rectangles(Vec<Vec<int>> a) {
const int n = (int) a.size();
const int m = (int) a[0].size();
Vec<Vec<Vec<int>>> row(n, Vec<Vec<int>>(m)), col(n, Vec<Vec<int>>(m));
for (int i = 0; i < n; ++i) {
Vec<int> stack;
for (int j = 0; j < m; ++j) {
int max = 0;
while (!stack.empty()) {
const int k = stack.back();
if (std::min(a[i][k], a[i][j]) > max and j - k > 1) {
row[i][j].push_back(k);
}
if (a[i][k] >= a[i][j]) {
break;
}
max = std::max(max, a[i][k]);
stack.pop_back();
}
stack.push_back(j);
}
}
for (int j = 0; j < m; ++j) {
Vec<int> stack;
for (int i = 0; i < n; ++i) {
int max = 0;
while (!stack.empty()) {
const int k = stack.back();
if (std::min(a[k][j], a[i][j]) > max and i - k > 1) {
col[i][j].push_back(k);
}
if (a[k][j] >= a[i][j]) {
break;
}
max = std::max(max, a[k][j]);
stack.pop_back();
}
stack.push_back(i);
}
}
Vec<Fenwick> fen(n, Fenwick(m));
Vec<Vec<std::pair<int, int>>> cand(m);
for (int j = 0; j < m; ++j) {
for (const int k : row[1][j]) {
cand[j].emplace_back(k, 1);
}
}
ll ret = 0;
for (int i = 2; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (const int k : col[i][j]) {
fen[k].add(j, 1);
}
for (const auto [a, l] : cand[j]) {
for (const int k : col[i][j - 1]) {
if (i - k - 1 > l) {
break;
}
if (fen[k].fold(a + 1, j) == j - a - 1) {
ret += 1;
}
}
}
}
for (int j = 0; j < m; ++j) {
for (const int k : col[i][j]) {
fen[k].add(j, -1);
}
Vec<std::pair<int, int>> next;
const auto& cur = cand[j];
const auto& add = row[i][j];
int x = 0, y = 0;
while (y < (int) add.size()) {
if (x < (int) cur.size() and cur[x].first == add[y]) {
next.emplace_back(cur[x].first, cur[x].second + 1);
x += 1;
y += 1;
} else if (x < (int) cur.size() and cur[x].first > add[y]) {
x += 1;
} else {
next.emplace_back(add[y], 1);
y += 1;
}
}
cand[j] = std::move(next);
}
}
return ret;
}
