// I can do all things through Christ who strengthens me
// Philippians 4:13
#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define SZ(x) (int) x.size()
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 2505;
int n, m;
vector<vi> a;
viii gdc, gdr;
vii mpr[MAXN][MAXN], mpc[MAXN][MAXN];
ll ans;
int fw[MAXN];
void incre(int i, int x) {
i++;
for (; i <= m; i += i & -i) {
fw[i] += x;
}
}
int qsm(int i) {
i++;
int res = 0;
for (; i > 0; i -= i & -i) {
res += fw[i];
}
return res;
}
ll count_rectangles(vector<vi> _a) {
a = _a;
n = SZ(a), m = SZ(a[0]);
REP (j, 1, m - 1) {
vi stk;
REP (i, 0, n) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
stk.pop_back();
}
if (!stk.empty() && stk.back() + 1 <= i - 1) {
gdc.pb({stk.back() + 1, i - 1, j});
}
stk.pb(i);
}
stk.clear();
RREP (i, n - 1, 0) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
stk.pop_back();
}
if (!stk.empty() && i + 1 <= stk.back() - 1) {
gdc.pb({i + 1, stk.back() - 1, j});
}
stk.pb(i);
}
}
REP (i, 1, n - 1) {
vi stk;
REP (j, 0, m) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
stk.pop_back();
}
if (!stk.empty() && stk.back() + 1 <= j - 1) {
gdr.pb({stk.back() + 1, j - 1, i});
}
stk.pb(j);
}
stk.clear();
RREP (j, m - 1, 0) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
stk.pop_back();
}
if (!stk.empty() && j + 1 <= stk.back() - 1) {
gdr.pb({j + 1, stk.back() - 1, i});
}
stk.pb(j);
}
}
sort(ALL(gdc));
gdc.erase(unique(ALL(gdc)), gdc.end());
cerr << "GDC:\n";
REP (i, 0, SZ(gdc)) {
auto [s, e, c] = gdc[i];
cerr << ' ' << s << ' ' << e << ' ' << c << '\n';
}
cerr << '\n';
REP (i, 0, SZ(gdc)) {
auto [s, e, c] = gdc[i];
int ni = SZ(gdc) - 1;
REP (j, i + 1, SZ(gdc)) {
auto [ns, ne, nc] = gdc[j];
if (s != ns || e != ne) {
ni = j - 1;
break;
}
}
int pc = INF, mxc = INF;
RREP (j, ni, i) {
auto [ns, ne, nc] = gdc[j];
if (nc + 1 != pc) {
mxc = nc;
}
pc = nc;
cerr << " " << s << ' ' << nc << ": " << e << ' ' << mxc << '\n';
mpc[s][nc].pb({e, mxc});
}
i = ni;
}
sort(ALL(gdr));
gdr.erase(unique(ALL(gdr)), gdr.end());
cerr << "GDR:\n";
REP (i, 0, SZ(gdr)) {
auto [s, e, c] = gdr[i];
cerr << ' ' << s << ' ' << e << ' ' << c << '\n';
}
cerr << '\n';
REP (i, 0, SZ(gdr)) {
auto [s, e, r] = gdr[i];
int ni = SZ(gdr) - 1;
REP (j, i + 1, SZ(gdr)) {
auto [ns, ne, nr] = gdr[j];
if (s != ns || e != ne) {
ni = j - 1;
break;
}
}
int pr = INF, mxr = INF;
RREP (j, ni, i) {
auto [ns, ne, nr] = gdr[j];
if (nr + 1 != pr) {
mxr = nr;
}
pr = nr;
mpr[nr][s].pb({mxr, e});
}
i = ni;
}
REP (i, 1, n - 1) {
REP (j, 1, m - 1) {
sort(ALL(mpc[i][j]), greater<ii>());
sort(ALL(mpr[i][j]), greater<ii>());
int ptr = 0;
cerr << i << ' ' << j << '\n';
for (auto [h, w] : mpc[i][j]) {
while (ptr < SZ(mpr[i][j]) && mpr[i][j][ptr].FI >= h) {
cerr << " + " << mpr[i][j][ptr].FI << ' ' << mpr[i][j][ptr].SE << '\n';
incre(mpr[i][j][ptr++].SE, 1);
}
int tmp = qsm(w);
cerr << " ? " << h << ' ' << w << ": " << tmp << '\n';
ans += tmp;
}
while (ptr > 0) {
incre(mpr[i][j][--ptr].SE, -1);
}
}
}
/*
REP (i, 1, n - 1) {
REP (j, 1, m - 1) {
REP (k, i, n - 1) {
REP (l, j, m - 1) {
if (!gdc[i][l][k]) {
break;
}
bool pos = 1;
REP (p, i, k + 1) {
if (!gdr[p][j][l]) {
pos = 0;
break;
}
}
ans += pos;
}
}
}
}
assert(ans <= n * m);
*/
return ans;
}
