#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> F(vector<int> A) {
int N = A.size();
vector<int> B(N, -1), stk;
for (int i = 0; i < N; i++) {
while (!stk.empty() && (A[stk.back()] < A[i])) {
stk.pop_back();
}
if (!stk.empty()) {
B[i] = stk.back();
}
stk.push_back(i);
}
return B;
}
vector<int> G(vector<int> A) {
int N = A.size();
vector<int> B(N);
for (int i = 0; i < N; i++) {
B[N - 1 - i] = N - 1 - A[i];
}
return B;
}
const int emax = -1;
int fmax(int x, int y) {
return max(x, y);
}
const int emin = 3000;
int fmin(int x, int y) {
return min(x, y);
}
const int N = 2500;
int lg[N + 1];
void init() {
lg[1] = 0;
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
}
template <int (*f)(int, int), int e>
struct sparse_table {
int n;
vector<vector<int>> st;
sparse_table() {
}
sparse_table(vector<int> a) : n(a.size()) {
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) {
assert(l <= r);
if (l == r) {
return e;
}
int k = lg[r - l];
return f(st[l][k], st[r - (1 << k)][k]);
}
};
using smin = sparse_table<fmin, emin>;
using smax = sparse_table<fmax, emax>;
long long count_rectangles(vector<vector<int>> A) {
init();
int N = A.size();
int M = A[0].size();
vector B(M, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
B[j][i] = A[i][j];
}
}
vector<vector<int>> L(N), R(N);
for (int i = 0; i < N; i++) {
L[i] = F(A[i]);
R[i] = G(F(vector(A[i].rbegin(), A[i].rend())));
}
vector<vector<int>> U(M), D(M);
for (int j = 0; j < M; j++) {
U[j] = F(B[j]);
D[j] = G(F(vector(B[j].rbegin(), B[j].rend())));
}
vector<smax> SL(M);
vector<smin> SR(M);
for (int j = 0; j < M; j++) {
vector<int> AL(N), AR(N);
for (int i = 0; i < N; i++) {
AL[i] = L[i][j];
AR[i] = R[i][j];
}
SL[j] = smax(AL);
SR[j] = smin(AR);
}
vector<smax> SU(N);
vector<smin> SD(N);
for (int i = 0; i < N; i++) {
vector<int> AU(M), AD(M);
for (int j = 0; j < M; j++) {
AU[j] = U[j][i];
AD[j] = D[j][i];
}
SU[i] = smax(AU);
SD[i] = smin(AD);
}
int ans = 0;
for (int x1 = 1; x1 < N; x1++) {
for (int x2 = x1 + 1; x2 < N; x2++) {
for (int y1 = 1; y1 < M; y1++) {
for (int y2 = y1 + 1; y2 < M; y2++) {
if (SR[y1 - 1].query(x1, x2) < y2) {
continue;
}
if (SD[x1 - 1].query(y1, y2) < x2) {
continue;
}
if (SL[y2].query(x1, x2) >= y1) {
continue;
}
if (SU[x2].query(y1, y2) >= x1) {
continue;
}
ans++;
}
}
}
}
return ans;
}
