#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 200 + 5, M = 200 + 5;
int n, m;
arr<arr<int, M>, N> a;
arr<arr<arr<int, M>, M>, N> up, dwn, vld, fr;
void prcmp() {
for (int j = 1; j <= m; j++) {
vec<int> x;
for (int i = n; i >= 1; i--) {
while (x.size() && a[x.back()][j] <= a[i][j]) {
up[x.back()][j][j] = i;
x.pop_back();
}
x.push_back(i);
}
while (x.size()) {
up[x.back()][j][j] = 0;
x.pop_back();
}
}
for (int j = 1; j <= m; j++) {
vec<int> x;
for (int i = 1; i <= n; i++) {
while (x.size() && a[x.back()][j] <= a[i][j]) {
dwn[x.back()][j][j] = i;
x.pop_back();
}
x.push_back(i);
}
while (x.size()) {
dwn[x.back()][j][j] = n + 1;
x.pop_back();
}
}
for (int i = 1; i <= n; i++) {
for (int l = 1; l <= m; l++) {
int mx = -1;
for (int r = l; r <= m; r++) {
if (r != l) {
up[i][l][r] = max(up[i][l][r - 1], up[i][r][r]);
dwn[i][l][r] = min(dwn[i][l][r - 1], dwn[i][r][r]);
}
mx = max(mx, a[i][r]);
if (l != 1 && r != m) vld[i][l][r] = (mx < min(a[i][l - 1], a[i][r + 1]));
}
}
}
for (int i = n; i >= 1; i--) {
for (int l = 1; l <= m; l++) {
for (int r = l; r <= m; r++) {
fr[i][l][r] = n + 1;
for (int j = i + 1; j <= n; j++)
if (!vld[j][l][r]) { fr[i][l][r] = j; break; }
// cout << i << " " << l << " " << r << ": " << dwn[i][l][r] << " " << fr[i][l][r] << '\n';
}
}
}
}
int cmp() {
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int l = 1; l <= m; l++) {
for (int r = l; r <= m; r++) {
int j = min({dwn[i][l][r], fr[i][l][r], n});
if (j < i + 2) continue;
// cout << i << " " << l << " " << r << ": " << i + 2 << " to " << j << '\n';
for (int k = i + 2; k <= j; k++)
ans += (up[k][l][r] <= i);
}
}
}
return ans;
}
int count_rectangles(vec<vec<sig>> _a) {
n = _a.size(), m = _a[0].size();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = _a[i - 1][j - 1];
prcmp();
return cmp();
}
