#include "rect.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=2500+1;
const double eps=1e-5;
const int mo=1e9+7;
int n,m;
ll a[N][N];
struct node {
int pos;
ll v;
};
node b[N];
int c[N],c2[N];
vector<int> e[N][N],e2[N][N];
bool cmp(node x,node y) {
if (x.v==y.v) return x.pos<y.pos;
return x.v>y.v;
}
vector<node> bit_q[N][N]; // q的树状数组
int l_max[N][N],u_max[N][N];
struct point {
int x,y;
};
vector<point> Q[N][N];
int far_up[N][N];
ll res;
int lowbit(int x) {
return x&-x;
}
void add(int x,int v,int len) {
int t=x;
while (x<=len) {
c[x]=max(c[x],v);
x+=lowbit(x);
}
x=len-t+1;
while (x<=len) {
c2[x]=min(c2[x],v);
x+=lowbit(x);
}
}
int getmax(int x) {
int ans=0;
while (x>=1) {
ans=max(ans,c[x]);
x-=lowbit(x);
}
return ans;
}
int getmin(int x,int len) {
x=len-x+1;
int ans=inf;
while (x>=1) {
ans=min(ans,c2[x]);
x-=lowbit(x);
}
return ans;
}
void uniquelize() {
FOR(i,n) FOR(j,m) {
vector<int> &v=e[i][j];
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
FOR(i,m) FOR(j,n) {
vector<int> &v=e2[i][j];
sort(v.begin(),v.end(),greater<int>());
v.erase(unique(v.begin(),v.end()),v.end());
}
}
void get_valid_interval() {
int p,pos,l,r,old_l,old_r;
FOR(i,n) {
FOR(j,m) c[j]=0,c2[j]=inf;
FOR(j,m) b[j].pos=j,b[j].v=a[i][j];
sort(b+1,b+1+m,cmp);
p=1,old_l=old_r=0;
FOR(j,m) {
if (j==m||b[j].v!=b[j+1].v) {
for (int k=p;k<=j;k++) {
pos=b[k].pos;
//if (old_l<=pos&&pos<=old_r) continue;
l=getmax(pos);
r=getmin(pos,m);
if (l!=0&&r!=inf) {
l++;r--;
e[i][l].pb(r);
old_l=l,old_r=r;
}
}
for (int k=p;k<=j;k++) {
pos=b[k].pos;
add(pos,pos,m);
}
p=j+1;
}
}
}
FOR(j,m) {
FOR(i,n) c[i]=0,c2[i]=inf;
FOR(i,n) b[i].pos=i,b[i].v=a[i][j];
sort(b+1,b+1+n,cmp);
p=1,old_l=old_r=0;
FOR(i,n) {
if (i==n||b[i].v!=b[i+1].v) {
for (int k=p;k<=i;k++) {
pos=b[k].pos;
//if (old_l<=pos&&pos<=old_r) continue;
l=getmax(pos);
r=getmin(pos,n);
if (l!=0&&r!=inf) {
l++;r--;
e2[j][r].pb(l);
old_l=l,old_r=r;
}
}
for (int k=p;k<=i;k++) {
pos=b[k].pos;
add(pos,pos,n);
}
p=i+1;
}
}
}
}
void get_Q(){
int x,y,sz;
FOR(i,n) {
FOR(j,m) {
sz=int(e2[j][i].size());
y=j;
for (int k=0;k<sz;k++) {
x=e2[j][i][k];
l_max[x][y]=l_max[x][y-1]+1;
Q[x][y-l_max[x][y]+1].pb(point{i,j});
}
}
FOR(j,m) {
sz=int(e2[j][i].size());
y=j;
for (int k=0;k<sz;k++) {
x=e2[j][i][k];
l_max[x][y]=0;
}
}
}
}
void get_bit_q() {
int sz;
FOR(i,n) FOR(j,m) {
sz=int(e2[j][i].size());
for (int k=0;k<sz;k++) {
bit_q[i][j].pb(node{e2[j][i][k],0});
}
}
}
void add2(vector<node> &a,int x,int v) {
int sz=int(a.size());
while (x<=sz) {
a[x-1].v+=v;
x+=lowbit(x);
}
}
int getsum(vector<node> &a,int x) {
int ans=0;
while (x>=1) {
ans+=a[x-1].v;
x-=lowbit(x);
}
return ans;
}
long long count_rectangles(std::vector<std::vector<int> > aa) {
n=aa.size();
m=aa[0].size();
FOR(i,n) {
FOR(j,m) {
a[i][j]=aa[i-1][j-1];
}
}
get_valid_interval();
uniquelize();
get_Q();
get_bit_q();
int sz,x,y,px,py,l,r,mid,ok_mid;
point q;
FOR(j,m) {
FOR(i,n) {
sz=int(e[i][j].size());
x=i;
for (int k=0;k<sz;k++) {
y=e[i][j][k];
u_max[x][y]=u_max[x-1][y]+1;
far_up[x][y]=x-u_max[x][y]+1;
}
}
FOR(i,n) {
sz=int(e[i][j].size());
x=i;
for (int k=0;k<sz;k++) {
y=e[i][j][k];
u_max[x][y]=0;
}
}
FOR(i,n) {
sz=Q[i][j].size();
for (int k=0;k<sz;k++) {
q=Q[i][j][k];
x=q.x,y=q.y;
px=i,py=q.y;
l=1,r=int(e2[y][x].size());
ok_mid=0;
// 找最小的>=px的数字
while (l<=r) {
mid=(l+r)/2;
if (e2[y][x][mid-1]>=px) {
l=mid+1;
ok_mid=mid;
} else r=mid-1;
}
if (ok_mid) add2(bit_q[x][y],ok_mid,1);
}
}
FOR(i,n) {
sz=int(e[i][j].size());
for (int k=0;k<sz;k++) {
y=e[i][j][k];
l=1,r=int(e2[y][i].size());
ok_mid=0;
while (l<=r) {
mid=(l+r)/2;
if (e2[y][i][mid-1]>=far_up[i][y]) {
l=mid+1;
ok_mid=mid;
} else r=mid-1;
}
if (ok_mid) {
res+=getsum(bit_q[i][y],ok_mid);
}
}
}
}
return res;
}
