#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) {
return lg[1000000];
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())));
for (int j = 0; j < M; j++) {
assert(L[i][j] >= -1 && L[i][j] < M);
assert(R[i][j] >= 0 && R[i][j] <= M);
}
}
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())));
for (int i = 0; i < N; i++) {
assert(U[j][i] >= -1 && U[j][i] < N);
assert(D[j][i] >= 0 && D[j][i] <= N);
}
}
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;
auto check = [&](int x1, int x2, int y1, int y2) {
if (SR[y1 - 1].query(x1, x2) < y2) return;
if (SD[x1 - 1].query(y1, y2) < x2) return;
if (SL[y2].query(x1, x2) >= y1) return;
if (SU[x2].query(y1, y2) >= x1) return;
ans++;
};
for (int i = 1; i < N - 1; i++) {
for (int j = 1; j < M - 1; j++) {
if (N - i >= M - j && 0) {
int u = R[i][j - 1];
int v = L[i][j + 1];
for (int k = i + 1; k < N; k++) {
if (j < u && u < M) {
check(i, k, j, u);
}
if (0 <= v && v < j && A[i][j + 1] != A[i][v]) {
check(i, k, v + 1, j + 1);
}
}
} else {
int u = D[j][i - 1];
int v = U[j][i + 1];
for (int k = j + 1; k < M; k++) {
if (i < u && u < N) {
check(i, u, j, k);
}
if (0 <= v && v < i && A[i + 1][j] != A[v][j]) {
check(v + 1, i + 1, j, k);
}
}
}
}
}
return ans;
}
