#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) {
continue;
}
int k = i;
while (k < N - 1 && (X[k][j - 1] == X[i][j - 1] || XR[k][X[i][j - 1]] == j - 1)) {
k++;
}
for (int x = i; x < k; x++) {
if (X[x][j - 1] != X[i][j - 1] || Y[x - 1][j] == -1 || Y[x - 1][j] > k || Y[x - 1][j] == x) {
continue;
}
bool ok = 1;
for (int y = j; y < X[i][j - 1]; y++) {
if (!(Y[x - 1][y] == Y[x - 1][j] || YR[Y[x - 1][j]][y] == x - 1)) {
ok = 0;
}
}
if (ok) {
ans++;
bool u = A[x][j - 1] == A[x][X[x][j - 1]];
bool v = A[x - 1][j] == A[Y[x - 1][j]][j];
if (u && v) {
D2++;
} else if (u || v) {
D1++;
}
}
}
}
}
swap(A, A2);
}
ans -= D1;
ans -= 3 * D2;
return ans;
}
