#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=2555,inf=1e8;
int n,m,a[N][N],L[N][N],D[N][N],U[N][N],R[N][N],fen[N][N],dp[N],mark[N],lupd[N][N],pd[N][N];
vector<int> lv[N][N];
vector<pair<int,int>> uv[N][N];
ll ans;
void ad(int x,int y,int val){
for(y++;y>0;y-=(y&-y)){
fen[x][y]+=val;
}
}
int gt(int x,int y){
int res=0;
for(y++;y<N;y+=(y&-y)){
res+=fen[x][y];
}
return res;
}
void add(int x,int y,int val){
for(x++;x<N;x+=(x&-x)){
ad(x,y,val);
}
}
int get(int x,int y){
int res=0;
for(x++;x>0;x-=(x&-x)){
res+=gt(x,y);
}
return res;
}
void do_it(){
f(i,1,n+1){
f(j,1,m+1){
U[i][j]=i-1;
while(a[U[i][j]][j]<a[i][j]){
U[i][j]=U[U[i][j]][j];
}
L[i][j]=j-1;
while(a[i][L[i][j]]<a[i][j]){
L[i][j]=L[i][L[i][j]];
}
if(a[U[i][j]][j]==a[i][j]){
U[i][j]=0;
}
if(a[i][L[i][j]]==a[i][j]){
L[i][j]=0;
}
if(U[i][j] && U[i][j]!=i-1){
uv[i][j].pb({U[i][j],0});
}
if(L[i][j] && L[i][j]!=j-1){
lv[i][j].pb(L[i][j]);
}
}
}
f_(i,n,1){
f_(j,m,1){
D[i][j]=i+1;
while(a[D[i][j]][j]<a[i][j]){
D[i][j]=D[D[i][j]][j];
}
R[i][j]=j+1;
while(a[i][R[i][j]]<a[i][j]){
R[i][j]=R[i][R[i][j]];
}
if(D[i][j]<=n && D[i][j]!=i+1){
uv[D[i][j]][j].pb({i,0});
}
if(R[i][j]<=m && R[i][j]!=j+1){
lv[i][R[i][j]].pb(j);
}
}
}
}
void edame(){
f(i,1,n+1){
f(j,1,m+1){
f(k,0,int(uv[i][j].size())){
int x=uv[i][j][k].F;
lupd[x][j]=i;
pd[x][j]=j;
if(lupd[x][j-1]==i){
pd[x][j]=pd[x][j-1];
}
uv[i][j][k].S=pd[x][j];
}
}
}
}
void solve(int y){
vector<pair<int,pair<int,int>>> op;
fill(dp,dp+N,N);
fill(mark,mark+N,0);
f(x,2,n){
for(auto u : lv[x][y]){
mark[u]=x;
if(dp[u]==N){
dp[u]=x;
//add(dp[u],u,1);
//op.pb({-1,{dp[u],u}});
}
add(dp[u],u,1);
}
for(auto u : lv[x-1][y]){
if(mark[u]==x-1){
//add(dp[u],u,-1);
//op.pb({+1,{dp[u],u}});
dp[u]=N;
}
}
for(auto p : uv[x+1][y-1]){
ans+=get(p.F+1,p.S-1);
}
for(auto u : lv[x][y]){
add(dp[u],u,-1);
}
//eror(ans);
}
for(auto p : op){
add(p.S.F,p.S.S,p.F);
}
//f(i,0,N) f(j,0,N) fen[i][j]=0;
}
ll count_rectangles(vector<vector<int>> T) {
n=T.size(),m=T[0].size();
f(i,0,n){
f(j,0,m){
a[i+1][j+1]=T[i][j]+1;
}
}
f(i,0,n+2){
f(j,0,m+2){
if(a[i][j]) continue ;
a[i][j]=inf;
}
}
do_it();
edame();
f(i,3,m+1){
solve(i);
}
//solve(5);
return ans;
}
/*
3 3
2 2 2
2 1 2
2 2 2
3 3
2 2 2
2 2 2
2 2 2
4 4
10 10 10 10
10 2 2 10
10 1 2 10
10 10 10 10
*/
