#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
int L, R, U, D;
T() {
L = U = -1;
R = D = 2500;
}
T(int x, int y, int z, int t) {
L = x;
R = y;
U = z;
D = t;
}
};
T F(T &a, T &b) {
return {max(a.L, b.L), min(a.R, b.R), max(a.U, b.U), min(a.D, b.D)};
}
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;
}
ll count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
bool subtask6 = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] > 1) {
subtask6 = 0;
}
}
}
int ans = 0;
if (subtask6) {
vector pfs(n, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pfs[i][j + 1] = pfs[i][j] + a[i][j];
}
}
vector<int> Q(n);
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
Q[i] = a[i][j] == 0 ? Q[i] + 1 : 0;
}
if (j == 0 || j == m - 1) {
continue;
}
for (int i = 1, k = 1; i < n - 1; i = k) {
while (k < n - 1 && (Q[i] == Q[k] && a[i][j + 1] == a[k][j + 1])) {
k++;
}
if (Q[i] > 0 && a[i][j + 1] == 1 && j - Q[i] >= 0 && pfs[i - 1][j + 1] - pfs[i - 1][j - Q[i] + 1] == Q[i] && pfs[k][j + 1] - pfs[k][j - Q[i] + 1] == Q[i]) {
ans++;
}
}
}
return ans;
}
vector S(n, vector<T>(m));
for (int i = 0; i < n; i++) {
auto l = ms(a[i], 0);
auto r = ms(a[i], 1);
for (int j = 0; j < m; j++) {
S[i][j].L = l[j];
S[i][j].R = r[j];
}
}
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++) {
S[i][j].U = u[i];
S[i][j].D = d[i];
}
}
auto check = [&](int x1, int y1, int x2, int y2) -> int {
if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
return 0;
}
for (int i = y1; i <= y2; i++) {
if (S[x1 - 1][i].D <= x2 || S[x2 + 1][i].U >= x1) {
return 0;
}
}
for (int i = x1; i <= x2; i++) {
if (S[i][y1 - 1].R <= y2 || S[i][y2 + 1].L >= y1) {
return 0;
}
}
return 1;
};
vector Q(n, vector<vector<int>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (S[i][j].U != -1) {
Q[S[i][j].U][j].push_back(i);
}
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
int y = S[i][j - 1].R - 1;
if (y != m - 1) {
int x = S[i - 1][j].D - 1;
if (x != n - 1) {
ans += check(i, j, x, y);
}
for (int k : Q[i - 1][j]) {
if (a[i - 1][j] != a[k][j]) {
ans += check(i, j, k - 1, y);
}
}
}
y = S[i][j + 1].L + 1;
if (y != 0 && a[i][j + 1] != a[i][y - 1]) {
int x = S[i - 1][j].D - 1;
if (x != n - 1) {
ans += check(i, y, x, j);
}
for (int k : Q[i - 1][j]) {
if (a[i - 1][j] != a[k][j]) {
ans += check(i, y, k - 1, j);
}
}
}
}
}
return ans;
}
