#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = 5e3;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define mp make_pair
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
struct stuff {
short coll, colr, rowl, rowr;
stuff(short coll = -INF, short colr = INF, short rowl = -INF, short rowr = INF) : coll(coll), colr(colr), rowl(rowl), rowr(rowr) {;;}
static stuff merge(const stuff &a, const stuff &b) {
return stuff{min(a.coll, b.coll), max(a.colr, b.colr), min(a.rowl, b.rowl), max(a.rowr, b.rowr)};
}
static ll calc(const stuff &a) {
// cerr << a.rowr - a.rowl - 1 sp a.colr - a.coll - 1 << endl;
return ll(a.rowr - a.rowl - 1) * ll(a.colr - a.coll - 1);
}
};
const stuff nothing = stuff{INF, -INF, INF, -INF};
short n, m;
int k;
const int dr[4] = {0, 0, -1, 1};
const int dc[4] = {-1, 1, 0, 0};
inline bool in(const short &x, const short &y) {
return (0 < x and x < n-1 and 0 < y and y < m-1);
}
inline ll encode(const ll &x, const ll &y, const ll &xx, const ll &yy) {
return ((x<<48)|(y<<32)|(xx<<16)|yy);
}
unordered_set<ll> vis;
ll count_rectangles(vector<vector<int>> a) {
n = a.size(), m = a[0].size(), k = n * m;
vector<vector<stuff>> base(n, vector<stuff>(m));
vis.reserve(1 << 20);
ll ans = 0;
vector<pair<int, int>> ts(k);
vector<int> st;
for (short i = 0; i < n; i++) {
st.clear();
for (short j = 0; j < m; j++) {
while (!st.empty() and a[i][st.back()] <= a[i][j]) {
st.pop_back();
}
if (!st.empty()) {
base[i][j].rowl = st.back();
}
st.push_back(j);
}
st.clear();
for (short j = m-1; j >= 0; j--) {
while (!st.empty() and a[i][st.back()] <= a[i][j]) {
st.pop_back();
}
if (!st.empty()) {
base[i][j].rowr = st.back();
}
st.push_back(j);
int ind = i * m + j;
ts[ind] = {a[i][j], ind};
}
}
for (short i = 0; i < m ; i++) {
st.clear();
for (short j = 0; j < n; j++) {
while (!st.empty() and a[st.back()][i] <= a[j][i]) {
st.pop_back();
}
if (!st.empty()) {
base[j][i].coll = st.back();
}
st.push_back(j);
}
st.clear();
for (short j = n-1; j >= 0; j--) {
while (!st.empty() and a[st.back()][i] <= a[j][i]) {
st.pop_back();
}
if (!st.empty()) {
base[j][i].colr = st.back();
}
st.push_back(j);
}
}
sort(all(ts), [&](const auto &a, const auto &b) -> bool {
return a.first < b.first;
});
vector<int> par(k), siz(k, 1);
vector<bool> vs(k, false);
iota(all(par), 0);
auto find = [&](auto &&find, int u) -> int {
if (u == par[u]) return u;
return par[u] = find(find, par[u]);
};
auto unite = [&](int u, int v) -> void {
u = find(find, u), v = find(find, v);
if (u == v) return;
// if (siz[u] < siz[v]) swap(u, v);
par[v] = u;
siz[u] += siz[v];
int ur = u / m, uc = u % m;
int vr = u / m, vc = u % m;
base[ur][uc] = stuff::merge(base[ur][uc], base[vr][vc]);
return;
};
auto ensure = [&](int u) -> bool {
int ur = u / m, uc = u % m;
// cerr << ur sp uc sp stuff::calc(base[ur][uc]) sp siz[u] << endl;
return stuff::calc(base[ur][uc]) <= siz[u];
};
auto check = [&](int r, int c) -> bool {
return 0 < r and r < n-1 and 0 < c and c < m-1;
};
for (int i = 0; i < k; i++) {
int hash = ts[i].second;
int r = hash / m, c = hash % m;
if (!check(r, c)) continue;
for (int j = 0; j < 4; j++) {
int nr = r + dr[j], nc = c + dc[j];
if (check(nr, nc) and vs[nr * m + nc]) {
// cerr << "un" sp nr sp nc << endl;
unite(hash, nr * m + nc);
}
}
if (ensure(find(find, hash))) ans++;
vs[hash] = true;
}
return ans;
}
// int main() {
// int n, m; cin >> n >> m;
// vector<vector<int>> a(n, vector<int>(m));
// REP(i, 0, n) {
// REP(j, 0, m) {
// cin >> a[i][j];
// }
// }
// cout << count_rectangles(a) << endl;
// }
