#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> ms(vector<int> &a, bool f) {
int n = a.size();
vector<int> b(n, f ? n : -1), stk;
for (int i = (f ? n - 1 : 0); i != (f ? -1 : n); i += (f ? -1 : 1)) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
b[i] = stk.back();
}
stk.push_back(i);
}
return b;
}
int lg[2501];
struct sparse_table {
int n, e;
int (*f)(int, int);
vector<vector<int>> st;
sparse_table() {
}
sparse_table(vector<int> &a, int (*_f)(int, int), int _e) : n(a.size()), f(_f), e(_e) {
st = vector(n, vector<int>(lg[n] + 1, e));
for (int i = 0; i < n; i++) {
st[i][0] = a[i];
}
for (int j = 0; j < lg[n]; j++) {
for (int i = 0; i + (2 << j) <= n; i++) {
st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
}
}
}
int query(int l, int r) {
if (l == r) {
return e;
}
int k = lg[r - l];
return f(st[l][k], st[r - (1 << k)][k]);
}
};
int fmin(int x, int y) {
return min(x, y);
}
int fmax(int x, int y) {
return max(x, y);
}
ll count_rectangles(vector<vector<int>> a) {
for (int i = 2; i <= 2500; i++) {
lg[i] = lg[i / 2] + 1;
}
int n = a.size();
int m = a[0].size();
vector L(n, vector<int>(m));
vector R(n, vector<int>(m));
vector D(n, vector<int>(m));
vector U(n, vector<int>(m));
for (int i = 0; i < n; i++) {
L[i] = ms(a[i], 0);
R[i] = ms(a[i], 1);
}
for (int j = 0; j < m; j++) {
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = a[i][j];
}
auto u = ms(v, 0);
auto d = ms(v, 1);
for (int i = 0; i < n; i++) {
U[i][j] = u[i];
D[i][j] = d[i];
}
}
vector<sparse_table> SL(m), SR(m), SU(n), SD(n);
for (int i = 0; i < n; i++) {
vector<int> u(m), d(m);
for (int j = 0; j < m; j++) {
u[j] = U[i][j];
d[j] = D[i][j];
}
SU[i] = sparse_table(u, fmax, -1);
SD[i] = sparse_table(d, fmin, n);
}
for (int i = 0; i < m; i++) {
vector<int> l(n), r(n);
for (int j = 0; j < n; j++) {
l[j] = L[j][i];
r[j] = R[j][i];
}
SL[i] = sparse_table(l, fmax, -1);
SR[i] = sparse_table(r, fmin, m);
}
auto check = [&](int x1, int y1, int x2, int y2) -> int {
if (SD[x1 - 1].query(y1, y2 + 1) <= x2) {
return 0;
}
if (SU[x2 + 1].query(y1, y2 + 1) >= x1) {
return 0;
}
if (SR[y1 - 1].query(x1, x2 + 1) <= y2) {
return 0;
}
if (SL[y2 + 1].query(x1, x2 + 1) >= y1) {
return 0;
}
return 1;
};
int ans = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
for (int x = i; x < n - 1; x++) {
for (int y = j; y < m - 1; y++) {
ans += check(i, j, x, y);
}
}
}
}
return ans;
}
