#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define INF 1023456789
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
#define maxn 2505
int n,m,ft[maxn+5];
vector<ii> h[maxn][maxn],v[maxn][maxn];
void up(int x,int v){
++x;
while(x<=maxn)ft[x]+=v,x+=x&-x;
}
int qry(int x,int y){
++y;int res=0;
while(y)res+=ft[y],y-=y&-y;
while(x)res-=ft[x],x-=x&-x;
return res;
}
ll count_rectangles(vector<vector<int>> a){
n=sz(a);m=sz(a[0]);
if(min(n,m)<=2)return 0;
for(int i=0;i<n;++i){
vector<ii> s;
s.pb({INF,-1});
for(int j=0;j<m;++j){
while(s.back().fi<a[i][j]){
if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
s.pop_back();
}
if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
s.pb({a[i][j],j});
}
}
for(int j=0;j<m;++j){
vector<ii> s;
s.pb({INF,-1});
for(int i=0;i<n;++i){
while(s.back().fi<a[i][j]){
if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
s.pop_back();
}
if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
s.pb({a[i][j],i});
}
}
for(int i=n-2;i>0;--i){
for(int j=m-2;j>0;--j){
for(ii &p:h[i][j]){
auto it=lower_bound(all(h[i+1][j]),p);
if(it!=h[i+1][j].end()&&(*it).fi==p.fi){
p.se=(*it).se;
}
}
for(ii &p:v[i][j]){
auto it=lower_bound(all(v[i][j+1]),p);
if(it!=v[i][j+1].end()&&(*it).fi==p.fi){
p.se=(*it).se;
}
}
}
}
for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(ii &p:h[i][j])swap(p.fi,p.se);
ll ans=0;
for(int i=1;i<n-1;++i){
for(int j=1;j<m-1;++j){
//pf("h[%d][%d]:\n",i,j);
//for(ii pr:h[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
//pf("v[%d][%d]:\n",i,j);
//for(ii pr:v[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
sort(all(h[i][j]),[](ii &a,ii &b){return a.se<b.se;});
sort(all(v[i][j]),[](ii &a,ii &b){return a.se<b.se;});
int curh=0,curv=0,mxh=sz(h[i][j]),mxv=sz(v[i][j]);
while(curv!=mxv){
while(curh!=mxh&&h[i][j][curh].se<=v[i][j][curv].se){
up(h[i][j][curh++].fi,1);
}
ans+=qry(v[i][j][curv++].fi,maxn-1);
}
for(int k=0;k<curh;++k)up(h[i][j][k].fi,-1);
}
}
return ans;
}
