#include <bits/stdc++.h>
using namespace std;
const int N = 2500;
short l[N][N], r[N][N], u[N][N], d[N][N];
short lu[N][N], ru[N][N], ul[N][N], dl[N][N];
short mono[N];
array<short, 4> rects[8 * N * N];
long long count_rectangles(vector<vector<int>> a) {
short n = a.size(), m = a[0].size();
for (short i = 0; i < n; ++i) {
for (short j = 0; j < m; ++j) {
l[i][j] = r[i][j] = u[i][j] = d[i][j] = -1;
}
}
for (short i = 0; i < n; ++i) {
short top = -1;
for (short j = 0; j < m; ++j) {
while (top >= 0 && a[i][mono[top]] < a[i][j]) {
short k = mono[top--];
if (k + 1 <= j - 1) {
r[i][k + 1] = j - 1;
}
}
if (top >= 0) {
short k = mono[top];
top -= a[i][k] == a[i][j];
if (k + 1 <= j - 1) {
l[i][j - 1] = k + 1;
}
}
mono[++top] = j;
}
}
for (short i = 0; i < m; ++i) {
short top = -1;
for (short j = 0; j < n; ++j) {
while (top >= 0 && a[mono[top]][i] < a[j][i]) {
short k = mono[top--];
if (k + 1 <= j - 1) {
d[k + 1][i] = j - 1;
}
}
if (top >= 0) {
short k = mono[top];
top -= a[k][i] == a[j][i];
if (k + 1 <= j - 1) {
u[j - 1][i] = k + 1;
}
}
mono[++top] = j;
}
}
for (short i = 0; i < n; ++i) {
for (short j = 0; j < m; ++j) {
if (l[i][j] != -1) {
if (i > 0 && l[i][j] == l[i - 1][j]) {
lu[i][j] = lu[i - 1][j];
} else if (i > 0 && r[i - 1][l[i][j]] == j) {
lu[i][j] = ru[i - 1][l[i][j]];
} else {
lu[i][j] = i;
}
}
if (r[i][j] != -1) {
if (i > 0 && r[i][j] == r[i - 1][j]) {
ru[i][j] = ru[i - 1][j];
} else if (i > 0 && l[i - 1][r[i][j]] == j) {
ru[i][j] = lu[i - 1][r[i][j]];
} else {
ru[i][j] = i;
}
}
}
}
for (short j = 0; j < m; ++j) {
for (short i = 0; i < n; ++i) {
if (u[i][j] != -1) {
if (j > 0 && u[i][j] == u[i][j - 1]) {
ul[i][j] = ul[i][j - 1];
} else if (j > 0 && d[u[i][j]][j - 1] == i) {
ul[i][j] = dl[u[i][j]][j - 1];
} else {
ul[i][j] = j;
}
}
if (d[i][j] != -1) {
if (j > 0 && d[i][j] == d[i][j - 1]) {
dl[i][j] = dl[i][j - 1];
} else if (j > 0 && u[d[i][j]][j - 1] == i) {
dl[i][j] = ul[d[i][j]][j - 1];
} else {
dl[i][j] = j;
}
}
}
}
int ans = 0;
for (short i1 = 0; i1 < n; ++i1) {
for (short j1 = 0; j1 < m; ++j1) {
for (auto i2 : {u[i1][j1], d[i1][j1]}) {
if (i2 == -1) {
continue;
}
for (auto i : {i1, i2}) {
for (auto j2 : {l[i][j1], r[i][j1]}) {
if (j2 == -1) {
continue;
}
short iu = min(i1, i2), id = max(i1, i2);
short jl = min(j1, j2), jr = max(j1, j2);
if (!(l[id][jr] == jl && lu[id][jr] <= iu) && !(r[id][jl] == jr && ru[id][jl] <= iu)) {
continue;
}
if (!(u[id][jr] == iu && ul[id][jr] <= jl) && !(d[iu][jr] == id && dl[iu][jr] <= jl)) {
continue;
}
rects[ans++] = {iu, id, jl, jr};
}
}
}
}
}
sort(rects, rects + ans);
return unique(rects, rects + ans) - rects;
}
