#include <bits/stdc++.h>
using namespace std;
#define C(X, Y) ((X)*m+Y)
const int Z = 2500;
struct SegmentTree {
int S[2*Z];
void operator()() {
for(int i = Z; --i; ) S[i] = max(S[2*i], S[2*i+1]);
}
int operator()(int l, int r) const {
int x = -1;
l += Z, r += Z + 1;
for(; l < r; l /= 2, r /= 2){
if(l & 1) x = max(x, S[l++]);
if(r & 1) x = max(x, S[--r]);
}
return x;
}
} s[4][Z];
int n, m, c[4][Z*Z], ans;
int sL[Z], *sR;
vector<array<int, 4>> q;
long long count_rectangles(vector<vector<int>> a) {
n = size(a), m = size(a[0]);
for(int i = 0; i < n; i++) {
for(int k : {0, 1}) {
sR = sL;
for(int j = 0; j < m; j++) {
while(sL != sR && a[i][sR[-1]] <= a[i][j]) --sR;
c[k][C(i, j)] = sL == sR ? -1 : sR[-1];
*sR++ = j;
}
reverse(begin(a[i]), end(a[i]));
}
for(int j = 0; j < m-1-j; j++)
swap(c[1][C(i, j)], c[1][C(i, m-1-j)]);
}
for(int j = 0; j < m; j++) {
for(int k : {2, 3}) {
sR = sL;
for(int i = 0; i < n; i++) {
while(sL != sR && a[sR[-1]][j] <= a[i][j]) --sR;
c[k][C(i, j)] = sL == sR ? -1 : sR[-1];
*sR++ = i;
}
for(int i = 0; i < n-1-i; i++)
swap(a[i][j], a[n-1-i][j]);
}
for(int i = 0; i < n-1-i; i++)
swap(c[3][C(i, j)], c[3][C(n-1-i, j)]);
}
for(int j = 0; j < m; j++) {
for(int k : {0, 1}) {
for(int i = 0; i < n; i++)
s[k][j].S[i+Z] = c[k][C(i, j)];
s[k][j]();
}
}
for(int i = 0; i < n; i++) {
for(int k : {2, 3}) {
for(int j = 0; j < m; j++)
s[k][i].S[j+Z] = c[k][C(i, j)];
s[k][i]();
}
}
q.reserve(n*m);
for(int i = n*m; --i >=0; ) {
if(min({c[0][i], c[1][i], c[2][i], c[3][i]}) >= 0)
q.push_back({c[0][i], m-1-c[1][i], c[2][i], n-1-c[3][i]});
}
sort(begin(q), end(q));
q.resize(unique(begin(q), end(q)) - begin(q));
for(auto &[j1, j2, i1, i2] : q) {
if(s[0][j2](i1+1, i2-1) > j1) continue;
if(s[2][i2](j1+1, j2-1) > i1) continue;
if(s[1][j1](i1+1, i2-1) > m-1-j2) continue;
if(s[3][i1](j1+1, j2-1) > n-1-i2) continue;
++ans;
}
return ans;
}
