#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int _N = 2501;
int A[_N][_N], L[_N][_N], R[_N][_N], U[_N][_N], D[_N][_N], IU[_N][_N], IL[_N][_N];
vector<pii> IR[_N][_N], ID[_N][_N];
long long count_rectangles(vector<vector<int>> a) {
int N = a.size(), M = a[0].size();
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) A[i][j] = a[i-1][j-1];
vector<int> S;
for(int i=1; i<=N; i++) {
S = {1};
for(int j=2; j<=M; j++) {
while(S.size() && A[i][S.back()] < A[i][j]) {
R[i][S.back()] = j;
S.pop_back();
}
S.push_back(j);
}
while(S.size()) {
R[i][S.back()] = M+1;
S.pop_back();
}
S = {M};
for(int j=M-1; j>=1; j--) {
while(S.size() && A[i][S.back()] <= A[i][j]) {
L[i][S.back()] = j;
S.pop_back();
}
S.push_back(j);
}
}
for(int j=1; j<=M; j++) {
S = {1};
for(int i=2; i<=N; i++) {
while(S.size() && A[S.back()][j] < A[i][j]) {
D[S.back()][j] = i;
S.pop_back();
}
S.push_back(i);
}
while(S.size()) {
D[S.back()][j] = N+1;
S.pop_back();
}
S = {N};
for(int i=N-1; i>=1; i--) {
while(S.size() && A[S.back()][j] <= A[i][j]) {
U[S.back()][j] = i;
S.pop_back();
}
S.push_back(i);
}
}
auto fnd = [&](vector<pii> &S, int v) {
int p = lower_bound(S.begin(), S.end(), make_pair(v, 0)) - S.begin();
if(p < S.size() && S[p].first == v) return S[p].second;
return 0;
};
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) {
if(1 <= L[i][j] && R[i][j] <= M && A[i][L[i][j]] > A[i][j]) {
IU[i][j] = i;
int v = fnd(IR[i-1][L[i][j]], R[i][j]);
if(v) IU[i][j] = v;
IR[i][L[i][j]].push_back({R[i][j], IU[i][j]});
}
}
for(int j=1; j<=M; j++) for(int i=1; i<=N; i++) {
if(1 <= U[i][j] && D[i][j] <= N && A[U[i][j]][j] > A[i][j]) {
IL[i][j] = j;
int v = fnd(ID[U[i][j]][j-1], D[i][j]);
if(v) IL[i][j] = v;
ID[U[i][j]][j].push_back({D[i][j], IL[i][j]});
}
}
vector<tuple<int, int, int, int>> V;
for(int i=2; i<N; i++) {
for(int j=2; j<M; j++) {
if(IU[i][j] && IL[i][j]) {
int vu = fnd(IR[D[i][j] - 1][L[i][j]], R[i][j]), vl = fnd(ID[U[i][j]][R[i][j] - 1], D[i][j]);
if(vu && vu <= U[i][j] + 1 && vl && vl <= L[i][j] + 1) V.push_back({L[i][j], R[i][j], U[i][j], D[i][j]});
}
}
}
sort(V.begin(), V.end());
return unique(V.begin(), V.end()) - V.begin();
}
