#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3
vector<int> next_geq_val(vector<int> v) {
int n = v.size();
stack<pair<int, int>> st;
st.push({1e9, n});
vector<int> ans(n);
for (int i = n-1; i >= 0; --i) {
while (st.top().first < v[i]) st.pop();
ans[i] = st.top().second;
st.push({v[i], i});
}
return ans;
}
vector<int> prev_geq_val(vector<int> v) {
int n = v.size();
reverse(v.begin(), v.end());
auto r = next_geq_val(v);
reverse(r.begin(), r.end());
for (int& i : r) {
i = n - 1 - i;
}
return r;
}
LL count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
vector<vector<array<int, 4>>> ext(n, vector<array<int, 4>>(m));
// LEFT & RIGHT
for (int i = 0; i < n; ++i) {
auto v = a[i];
auto nxt = next_geq_val(v);
auto prv = prev_geq_val(v);
for (int j = 0; j < m; ++j) {
ext[i][j][LEFT] = prv[j];
ext[i][j][RIGHT] = nxt[j];
}
}
// UP & DOWN
for (int j = 0; j < m; ++j) {
vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = a[i][j];
auto nxt = next_geq_val(v);
auto prv = prev_geq_val(v);
for (int i = 0; i < n; ++i) {
ext[i][j][UP] = prv[i];
ext[i][j][DOWN] = nxt[i];
}
}
LL ans = 0;
for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) {
int rwall = m-1;
for (int rr = r+2; rr < n; ++rr) {
rwall = min(rwall, ext[rr-1][c][RIGHT]);
int dwall = n-1;
for (int cc = c+2; cc <= rwall; ++cc) {
dwall = min(dwall, ext[r][cc-1][DOWN]);
if (rr > dwall) break;
bool works = true;
// orizzontali
for (int j = c+1; works && j < cc; ++j) {
works &= (ext[r][j][DOWN] >= rr);
works &= (ext[rr][j][UP] <= r);
}
// verticali
for (int i = r+1; works && i < rr; ++i) {
works &= (ext[i][c][RIGHT] >= cc);
works &= (ext[i][cc][LEFT] <= c);
}
ans += works;
}
}
}
return ans;
}
