#include <bits/stdc++.h>
using namespace std;
const int N = 2500;
map<short, short> where_h[N][N], where_v[N][N];
short jump_h[N][N][2], jump_v[N][N][2];
array<short, 4> rects[8 * N * N];
void update(map<short, short> &s, short a) {
short l = a;
auto nxt = s.upper_bound(a);
if (nxt != s.begin()) {
auto prv = nxt; --prv;
if (prv->second + 1 == a) {
l = prv->first;
}
}
short r = a;
if (nxt != s.end() && nxt->first - 1 == a) {
r = nxt->second;
s.erase(nxt);
}
s[l] = r;
}
bool query(map<short, short> &s, short a, short b) {
auto it = s.upper_bound(a);
return it != s.begin() && (--it)->second >= b;
}
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) {
for (short k = 0; k < 2; ++k) {
jump_h[i][j][0] = jump_v[i][j][0] = -1;
}
}
}
for (short i = 0; i < n; ++i) {
vector<short> mono;
for (short j = 0; j < m; ++j) {
bool equal = false;
while (!mono.empty() && a[i][mono.back()] <= a[i][j]) {
short k = mono.back();
mono.pop_back();
equal = a[i][k] == a[i][j];
if (k + 1 <= j - 1) {
update(where_h[k + 1][j - 1], i);
jump_h[i][k + 1][1] = j - 1;
}
}
if (!mono.empty() && !equal) {
short k = mono.back();
if (k + 1 <= j - 1) {
update(where_h[k + 1][j - 1], i);
jump_h[i][j - 1][0] = k + 1;
}
}
mono.push_back(j);
}
}
for (short i = 0; i < m; ++i) {
vector<short> mono;
for (short j = 0; j < n; ++j) {
bool equal = false;
while (!mono.empty() && a[mono.back()][i] <= a[j][i]) {
short k = mono.back();
mono.pop_back();
equal = a[k][i] == a[j][i];
if (k + 1 <= j - 1) {
update(where_v[k + 1][j - 1], i);
jump_v[k + 1][i][1] = j - 1;
}
}
if (!mono.empty() && !equal) {
short k = mono.back();
if (k + 1 <= j - 1) {
update(where_v[k + 1][j - 1], i);
jump_v[j - 1][i][0] = k + 1;
}
}
mono.push_back(j);
}
}
int ans = 0;
for (short a = 0; a < n; ++a) {
for (short b = 0; b < m; ++b) {
for (auto c : jump_v[a][b]) {
if (c != -1) {
for (auto d : {a, c}) {
for (auto e : jump_h[d][b]) {
if (e != -1) {
short w = min(a, c), x = max(a, c);
short y = min(b, e), z = max(b, e);
if (query(where_v[w][x], y, z) && query(where_h[y][z], w, x)) {
rects[ans++] = {w, x, y, z};
}
}
}
}
}
}
}
}
sort(rects, rects + ans);
return unique(rects, rects + ans) - rects;
}
