#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii int32_t
#define int int16_t
using pii = pair<int, int>;
#define X first
#define Y second
const int MXN = 2501;
int n, m;
vector<pii> vr[MXN][MXN], vd[MXN][MXN];
int L[MXN][MXN], R[MXN][MXN];
int stk[MXN], szx, ord[MXN];
int fen[MXN];
inline void updx(int p, int x) {
for(++p; p<=m; p+=p&-p) fen[p] += x;
}
inline int getx(int p) {
int res=0;
for(++p; p; p-=p&-p) res += fen[p];
return res;
}
ll count_rectangles(vector<vector<ii>> a) {
n = a.size(), m = a[0].size();
if(n<=2 || m<=2) return 0;
for(int l=0; l<m; l++)
for(int r=l; r<m; r++)
L[l][r] = n+5;
for(int i=n-2; i>=1; i--) {
szx = 0;
for(int j=m-1; j>=0; j--) {
while(szx && a[i][stk[szx-1]]<a[i][j]) {
if(j+1<stk[szx-1]) vr[i][j+1].push_back({stk[szx-1]-1, 0});
szx--;
}
if(szx) {
if(j+1<stk[szx-1]) vr[i][j+1].push_back({stk[szx-1]-1, 0});
if(a[i][stk[szx-1]]==a[i][j]) szx--;
}
stk[szx++] = j;
}
for(int l=1, sz; l+1<m; l++) {
sz = vr[i][l].size();
for(int j=0, r; j<sz; j++) {
r = vr[i][l][j].X;
if(L[l][r]==i+1) {
vr[i][l][j].Y = R[l][r];
L[l][r] = i;
}
else
vr[i][l][j].Y = L[l][r] = R[l][r] = i;
}
}
}
for(int l=0; l<n; l++)
for(int r=l; r<n; r++)
L[l][r] = m+5;
for(int j=m-2; j>=1; j--) {
szx = 0;
for(int i=n-1; i>=0; i--) {
while(szx && a[stk[szx-1]][j]<a[i][j]) {
if(i+1<stk[szx-1]) vd[i+1][j].push_back({stk[szx-1]-1, 0});
szx--;
}
if(szx) {
if(i+1<stk[szx-1]) vd[i+1][j].push_back({stk[szx-1]-1, 0});
if(a[stk[szx-1]][j]==a[i][j]) szx--;
}
stk[szx++] = i;
}
for(int l=1, sz; l+1<n; l++) {
sz = vd[l][j].size();
for(int i=0, r; i<sz; i++) {
r = vd[l][j][i].X;
if(L[l][r]==j+1) {
vd[l][j][i].Y = R[l][r];
L[l][r] = j;
}
else
vd[l][j][i].Y = L[l][r] = R[l][r] = j;
}
}
}
ll ans = 0;
for(int i=0, sr, sd; i<n; i++)
for(int j=0; j<m; j++) {
sr = vr[i][j].size();
sd = vd[i][j].size();
iota(ord, ord+sr, 0);
sort(ord, ord+sr, [&](int x, int y) {
return vr[i][j][x].Y<vr[i][j][y].Y;
});
int p1=0, p2=0;
while(p1<sr && p2<sd) {
if(vd[i][j][p2].X<=vr[i][j][ord[p1]].Y)
updx(vd[i][j][p2++].Y, 1);
else
ans += p2-getx(vr[i][j][ord[p1++]].X-1);
}
while(p1<sr)
ans += p2-getx(vr[i][j][ord[p1++]].X-1);
while((--p2)>=0)
updx(vd[i][j][p2].Y, -1);
}
return ans;
}
