#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,m,nm=0,nn[2],a[2501][2501],dsu[2][2501],ls[2501],vl[2501][2501],fq[2501];
pair<int,int> as[2501];
pair<pair<int,int>,int> ass[6250001],dp[2][2501];
inline int val(int xx,int y,int x)
{
if(!xx)
{
swap(y,x);
}
return a[y][x];
}
int fd(int xx,int x)
{
if(dsu[xx][x]!=x)
{
dsu[xx][x]=fd(xx,dsu[xx][x]);
}
return dsu[xx][x];
}
long long count_rectangles(vector<vector<int>> aa)
{
int rr,i,j,r,r2,ii,u,k,l,w,cr,tg,pp,kk,p,tmp[2501],c,z=0;
n=aa.size();
m=aa[0].size();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]=aa[i-1][j-1];
}
}
for(rr=0;rr<2;rr++)
{
swap(n,m);
if(rr)
{
sort(ass+1,ass+nm+1);
pp=1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
as[j]={val(rr,i,j),j};
for(ii=0;ii<2;ii++)
{
dsu[ii][j]=j;
}
ls[j]=0;
if(rr)
{
fq[j]=0;
}
}
sort(as+1,as+m+1);
for(;pp<=nm&&ass[pp].fr.fr<=i;pp++)
{
k=ass[pp].sc;
w=ass[pp].fr.sc;
fq[k]++;
vl[k][fq[k]]=w;
}
l=0;
for(j=1;j<=m;j++)
{
k=as[j].sc;
w=as[j].fr;
for(u=-1;u<=1;u+=2)
{
if(k+u&&k+u<=m&&val(rr,i,k+u)<=val(rr,i,k))
{
if(rr)
{
cr=fd(0,k);
tg=fd(0,k+u);
c=0;
for(r=1;r<=fq[cr];r++)
{
kk=vl[cr][r];
p=lower_bound(vl[tg]+1,vl[tg]+fq[tg]+1,kk)-vl[tg];
if(p<=fq[tg]&&vl[tg][p]==kk)
{
c++;
tmp[c]=kk;
}
}
}
for(ii=0;ii<2;ii++)
{
dsu[ii][fd(ii,k-ii+(u+1)/2)]=fd(ii,k-1+ii+(u+1)/2);
}
if(rr)
{
cr=fd(0,k);
fq[cr]=c;
for(r=1;r<=c;r++)
{
vl[cr][r]=tmp[r];
}
}
}
}
if(j==m||w!=as[j+1].fr)
{
for(r=l+1;r<=j;r++)
{
k=as[r].sc;
cr=fd(0,k);
tg=fd(1,k);
if(ls[cr]<j)
{
ls[cr]=j;
if(!rr)
{
nm++;
ass[nm]={{tg,cr},i};
}
else
{
p=lower_bound(dp[0]+1,dp[0]+nn[0]+1,mp(mp(cr,tg),0))-dp[0];
w=1;
if(p<=nn[0]&&dp[0][p].fr.fr==cr&&dp[0][p].fr.sc==tg)
{
w+=dp[0][p].sc;
}
nn[1]++;
dp[1][nn[1]]={{cr,tg},w};
for(r2=1;r2<=fq[cr];r2++)
{
kk=vl[cr][r2];
z+=i-kk+1<=w&&kk>1&&cr>1&&i<n&&tg<m;
}
}
}
}
l=j;
}
}
if(rr)
{
nn[0]=nn[1];
for(j=1;j<=nn[0];j++)
{
dp[0][j]=dp[1][j];
}
sort(dp[0]+1,dp[0]+nn[0]+1);
nn[1]=0;
}
}
}
return z;
}
