#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
const ll MAXN = 1<<12;
const short INF = MAXN+16;
short gi1[MAXN][MAXN], gi2[MAXN][MAXN], gj1[MAXN][MAXN], gj2[MAXN][MAXN];
using dat = pair <pair <short, short>, pair <short, short> >;
dat operator+ (const dat &a, const dat &b) {
return dat{
{ min(a.first.first, b.first.first),
min(a.first.second, b.first.second) },
{ max(a.second.first, b.second.first),
max(a.second.second, b.second.second) }
};
}
const dat IDEM = { { INF, INF }, { -INF, -INF } };
const dat OVER = { { -INF, -INF }, { INF, INF } };
dat mat[MAXN][MAXN];
ll count_rectangles (vector <vi> a) {
ll n = a.size(), m = a[0].size();
for (ll i = 0; i < n; i++) {
vii stk;
stk.push_back({ INF, -1 });
for (ll j = 0; j < m; j++) {
while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
gj1[i][j] = stk.back().second+1;
stk.push_back({ a[i][j], j });
}
}
for (ll i = 0; i < n; i++) {
vii stk;
stk.push_back({ INF, m });
for (ll j = m-1; j >= 0; j--) {
while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
gj2[i][j] = stk.back().second-1;
stk.push_back({ a[i][j], j });
}
}
for (ll j = 0; j < m; j++) {
vii stk;
stk.push_back({ INF, -1 });
for (ll i = 0; i < n; i++) {
while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
gi1[i][j] = stk.back().second+1;
stk.push_back({ a[i][j], i });
}
}
for (ll j = 0; j < m; j++) {
vii stk;
stk.push_back({ INF, n });
for (ll i = n-1; i >= 0; i--) {
while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
gi2[i][j] = stk.back().second-1;
stk.push_back({ a[i][j], i });
}
}
priority_queue <pair <ll, ii> > pq;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
pq.push({ -a[i][j], { i, j } });
}
}
for (ll i1 = 0; i1 < max(n,m); i1++) {
for (ll i2 = 0; i2 < max(n,m); i2++) {
mat[i1][i2] = OVER;
}
}
ll ans = 0;
while (pq.size()) {
auto [i, j] = pq.top().second; pq.pop();
ll i1 = gi1[i][j];
ll j1 = gj1[i][j];
ll i2 = gi2[i][j];
ll j2 = gj2[i][j];
mat[i][j] = { { i1, j1 }, { i2, j2 } };
dat th = IDEM;
for (ll ii = i1; ii <= i2; ii++)
for (ll jj = j1; jj <= j2; jj++)
th = th + mat[ii][jj];
// cerr << i << ' ' << j << " ";
// cerr << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n';
// auto [p1,p2]=s;
// auto [p3,p4]=p1;
// auto [p5,p6]=p2;
// cerr << p3 << ' '<< p4 << ' ' << p5 << ' ' << p6 << '\n';
if (th == dat{ { i1, j1 }, { i2, j2 } } && 0 < i1 && i2 < n-1 && 0 < j1 && j2 < m-1) ans++;
}
return ans;
}
