#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "rect.h"
using namespace std;
using LL = long long;
struct fenwick {
int n;
vector<int> t;
fenwick(int _n) : n(_n), t(_n) {
}
void modify(int x, int v) {
for (int i = x + 1; i; i -= i & -i) {
t[i - 1] += v;
}
}
int get(int x) {
int r = 0;
for (int i = x + 1; i <= n; i += i & -i) {
r += t[i - 1];
}
return r;
}
};
struct DS {
vector<array<int, 2>> p, q;
DS() = default;
void insert(int x, int y) {
p.push_back({x, y});
}
void query(int x, int y) {
q.push_back({x, y});
}
int solve() {
int res = 0;
sort(p.begin(), p.end()), sort(q.begin(), q.end());
int idx = 0;
static fenwick tr(2500);
for (auto [x, y] : q) {
while (idx < p.size() && p[idx][0] <= x) {
tr.modify(p[idx++][1], 1);
}
res += tr.get(y);
}
while (idx) {
tr.modify(p[--idx][1], -1);
}
return res;
}
};
LL count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<array<int, 2>>> avc(n), avr(m);
for (int r = 0; r < n; r++) {
vector<int> lef(m), rgt(m);
{
stack<int> st;
for (int c = 1; c <= m - 2; c++) {
while (st.size() && a[r][st.top()] <= a[r][c]) {
st.pop();
}
if (st.empty()) {
lef[c] = 1;
} else {
lef[c] = st.top() + 1;
}
st.push(c);
}
}
{
stack<int> st;
for (int c = m - 2; c >= 1; c--) {
while (st.size() && a[r][st.top()] <= a[r][c]) {
st.pop();
}
if (st.empty()) {
rgt[c] = m - 2;
} else {
rgt[c] = st.top() - 1;
}
st.push(c);
}
}
for (int i = 1; i <= m - 2; i++) {
if (a[r][i] < min(a[r][lef[i] - 1], a[r][rgt[i] + 1])) {
avc[r].push_back({lef[i], rgt[i]});
}
}
sort(avc[r].begin(), avc[r].end()), avc[r].erase(unique(avc[r].begin(), avc[r].end()), avc[r].end());
}
for (int c = 0; c < m; c++) {
vector<int> lef(n), rgt(n);
{
stack<int> st;
for (int r = 1; r <= n - 2; r++) {
while (st.size() && a[st.top()][c] <= a[r][c]) {
st.pop();
}
if (st.empty()) {
lef[r] = 1;
} else {
lef[r] = st.top() + 1;
}
st.push(r);
}
}
{
stack<int> st;
for (int r = n - 2; r >= 1; r--) {
while (st.size() && a[st.top()][c] <= a[r][c]) {
st.pop();
}
if (st.empty()) {
rgt[r] = n - 2;
} else {
rgt[r] = st.top() - 1;
}
st.push(r);
}
}
for (int i = 1; i <= n - 2; i++) {
if (a[i][c] < min(a[lef[i] - 1][c], a[rgt[i] + 1][c])) {
avr[c].push_back({lef[i], rgt[i]});
}
}
sort(avr[c].begin(), avr[c].end()), avr[c].erase(unique(avr[c].begin(), avr[c].end()), avr[c].end());
}
vector<vector<int>> down(n), right(m);
for (int i = n - 2; i >= 1; i--) {
down[i].resize(avc[i].size());
for (int j = 0; j < avc[i].size(); j++) {
auto it = avc[i][j];
int where = lower_bound(avc[i + 1].begin(), avc[i + 1].end(), it) - avc[i + 1].begin();
if (i == n - 2 || (where == avc[i + 1].size() || avc[i + 1][where] != it)) {
down[i][j] = i;
} else {
down[i][j] = down[i + 1][where];
}
}
}
for (int i = m - 2; i >= 1; i--) {
right[i].resize(avr[i].size());
for (int j = 0; j < avr[i].size(); j++) {
auto it = avr[i][j];
int where = lower_bound(avr[i + 1].begin(), avr[i + 1].end(), it) - avr[i + 1].begin();
if (i == m - 2 || (where == avr[i + 1].size() || avr[i + 1][where] != it)) {
right[i][j] = i;
} else {
right[i][j] = right[i + 1][where];
}
}
}
vector d(n, vector<DS>(m));
for (int c = 1; c <= m - 2; c++) {
for (int i = 0; i < avr[c].size(); i++) {
auto [L, R] = avr[c][i];
d[L][c].insert(R, right[c][i]);
}
}
for (int r = 1; r <= n - 2; r++) {
for (int i = 0; i < avc[r].size(); i++) {
auto [L, R] = avc[r][i];
d[r][L].query(down[r][i], R);
}
}
LL ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += d[i][j].solve();
}
}
return ans;
}
