#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);
}
long long ans = 0;
for (int r1 = 1; r1 < n - 1; r1++) {
for (int r2 = r1; r2 < n - 1; r2++) {
for (int c1 = 1; c1 < m - 1; c1++) {
for (int c2 = c1; c2 < m - 1; c2++) {
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;
}
