#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> F(vector<int> A) {
int N = A.size();
vector<int> B(N), stk{-1};
for (int i = 0; i < N; i++) {
while (stk.back() != -1 && (A[stk.back()] < A[i])) {
stk.pop_back();
}
B[i] = stk.back();
stk.push_back(i);
}
return B;
}
vector<int> R(vector<int> A) {
int N = A.size();
vector<int> B(N);
for (int i = 0; i < N; i++) {
if (A[i] == -1) {
B[N - 1 - i] = -1;
} else {
B[N - 1 - i] = N - 1 - A[i];
}
}
return B;
}
long long count_rectangles(vector<vector<int>> A) {
int N = A.size();
int M = A[0].size();
int ans = 0, D1 = 0, D2 = 0;
for (int mask = 0; mask < 4; mask++) {
vector A2(N, vector<int>(M));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
A2[mask % 2 == 0 ? i : N - 1 - i][mask / 2 % 2 == 0 ? j : M - 1 - j] = A[i][j];
}
}
swap(A, A2);
vector<vector<int>> X(N), XR(N);
for (int i = 0; i < N; i++) {
X[i] = R(F(vector(A[i].rbegin(), A[i].rend())));
XR[i] = F(A[i]);
}
vector Y(N, vector<int>(M));
vector YR(N, vector<int>(M));
for (int j = 0; j < M; j++) {
vector<int> B(N);
for (int i = 0; i < N; i++) {
B[i] = A[i][j];
}
auto C = R(F(vector(B.rbegin(), B.rend())));
auto D = F(B);
for (int i = 0; i < N; i++) {
Y[i][j] = C[i];
YR[i][j] = D[i];
}
}
for (int j = 1; j < M - 1; j++) {
for (int i = 1; i < N - 1; i++) {
if (X[i][j - 1] == -1 || X[i][j - 1] == j || Y[i - 1][j] == -1 || Y[i - 1][j] == i) {
continue;
}
bool ok = 1;
int i2 = Y[i - 1][j];
int j2 = X[i][j - 1];
for (int x = i; x < i2; x++) {
for (int y = j; y < j2; y++) {
if (A[x][y] >= min({A[x][j - 1], A[x][j2], A[i - 1][y], A[i2][y]})) {
ok = 0;
}
}
}
if (ok) {
ans++;
bool u = A[i][j - 1] == A[i][j2];
bool v = A[i - 1][j] == A[i2][j];
if (u && v) {
D2++;
} else if (u || v) {
D1++;
}
}
}
}
swap(A, A2);
}
ans -= D1 / 2;
ans -= D2 / 4 * 3;
return ans;
}
