#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "rect.h"
using namespace std;
using LL = long long;
int fenwick[2500];
inline void modify(int x, int v) {
for (int i = x + 1; i; i -= i & -i) {
fenwick[i - 1] += v;
}
}
inline int get(int x) {
int r = 0;
for (int i = x + 1; i <= 2500; i += i & -i) {
r += fenwick[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;
for (const auto &[x, y] : q) {
while (idx < p.size() && p[idx][0] <= x) {
modify(p[idx++][1], 1);
}
res += get(y);
}
while (idx) {
modify(p[--idx][1], -1);
}
return res;
}
} d[2500][2500];
vector<array<int, 2>> avc[2500], avr[2500];
vector<int> down[2500], rght[2500];
int lef[2500], rgt[2500];
int Where[2500][2500];
LL count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int r = 1; r <= n - 2; r++) {
{
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 = 1; c <= m - 2; c++) {
{
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());
}
memset(Where, -1, sizeof Where);
for (int i = n - 2; i >= 1; i--) {
down[i].resize(avc[i].size());
for (int j = 0; j < avc[i + 1].size(); j++) {
auto [x, y] = avc[i + 1][j];
Where[x][y] = j;
}
for (int j = 0; j < avc[i].size(); j++) {
auto it = avc[i][j];
int where = Where[it[0]][it[1]];
if (where == -1 || i == n - 2) {
down[i][j] = i;
} else {
down[i][j] = down[i + 1][where];
}
}
for (auto [x, y] : avc[i + 1]) {
Where[x][y] = -1;
}
}
for (int i = m - 2; i >= 1; i--) {
rght[i].resize(avr[i].size());
for (int j = 0; j < avr[i + 1].size(); j++) {
auto [x, y] = avr[i + 1][j];
Where[x][y] = j;
}
for (int j = 0; j < avr[i].size(); j++) {
auto it = avr[i][j];
int where = Where[it[0]][it[1]];
if (where == -1) {
rght[i][j] = i;
} else {
rght[i][j] = rght[i + 1][where];
}
}
for (auto [x, y] : avr[i + 1]) {
Where[x][y] = -1;
}
}
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, rght[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 = 1; i <= n - 2; i++) {
for (int j = 1; j <= m - 2; j++) {
ans += d[i][j].solve();
}
}
return ans;
}
