#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
struct SparseTable {
int n;
vector<vector<int>> t;
vector<int> lg;
void init(vector<int> a) {
n = a.size();
lg.resize(n + 1);
t.resize(n, vector<int>(10));
build(a);
}
void build(vector<int> a) {
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 0; i < n; i++) {
t[i][0] = a[i];
}
for (int j = 1; j < 10; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
t[i][j] = max(t[i][j - 1], t[i + (1 << (j - 1))][j - 1]);
}
}
}
int get(int l, int r) {
int x = lg[r - l + 1];
return max(t[l][x], t[r - (1 << x) + 1][x]);
}
};
long long count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<SparseTable> r(n), c(m);
for (int i = 0; i < n; i++) {
r[i].init(a[i]);
}
for (int i = 0; i < m; i++) {
vector<int> x;
for (int j = 0; j < n; j++) {
x.push_back(a[j][i]);
}
c[i].init(x);
}
vector<array<int, 2>> top_left, bottom_right;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (a[i][j] < max(a[i - 1][j], a[i][j - 1])) {
top_left.push_back({i, j});
}
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m - 1; j++) {
if (a[i][j] < max(a[i + 1][j], a[i][j + 1])) {
bottom_right.push_back({i, j});
}
}
}
long long ans = 0;
for (auto [r1, c1] : top_left) {
for (auto [r2, c2] : bottom_right) {
if (r2 < r1 || c2 < c1) continue;
bool ok = true;
for (int i = r1; i <= r2; i++) {
if (r[i].get(c1, c2) >= min(a[i][c1 - 1], a[i][c2 + 1])) {
ok = false;
break;
}
}
if (!ok) continue;
for (int i = c1; i <= c2; i++) {
if (c[i].get(r1, r2) >= min(a[r1 - 1][i], a[r2 + 1][i])) {
ok = false;
break;
}
}
if (ok) {
ans++;
}
}
}
return ans;
}
