#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2509;
const int inf=7e6+9;
struct ST{
vector<int>mx,mn;
void resz(int n){
mx.resize(4*n+9);
mn.resize(4*n+9);
}
void update(int id,int l,int r,int u,int v1,int v2){
if (l>u||r<u)return;
if (l==r){
mx[id]=v2;
mn[id]=v1;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,v1,v2);
update(id*2+1,mid+1,r,u,v1,v2);
mx[id]=max(mx[id*2],mx[id*2+1]);
mn[id]=min(mn[id*2],mn[id*2+1]);
}
int getmin(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 2509;
if (u<=l&&r<=v)return mn[id];
int mid=(l+r)/2;
return min(getmin(id*2,l,mid,u,v),getmin(id*2+1,mid+1,r,u,v));
}
int getmax(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return mx[id];
int mid=(l+r)/2;
return max(getmax(id*2,l,mid,u,v),getmax(id*2+1,mid+1,r,u,v));
}
};
struct BIT{
vector<int>bit;
int n;
void resz(int _n){
n=_n;
bit.resize(n+1);
}
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int m,n;
int up[maxn][maxn],down[maxn][maxn],a[maxn][maxn];
set<int>b[maxn][maxn];
ST st[maxn];
vector<int>del[maxn];
void build(){
//up[i][j]=i1 j i1<i a[i1][j]>=a[i][j]
for1(j,1,n){
stack<int>t;
t.push(0);
a[0][j]=inf;
for1(i,1,m){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
up[i][j]=t.top();
t.push(i);
}
}
for1(j,1,n){
a[m+1][j]=inf;
stack<int>t;
t.push(m+1);
for2(i,m,1){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
down[i][j]=t.top();
t.push(i);
}
}
for1(i,1,m){
a[i][n+1]=inf;
stack<int>t;
t.push(n+1);
for2(j,n,1){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
//cout<<i<<" "<<j<<" "<<t.top()<<'\n';
if (t.top()!=n+1){
b[i][t.top()].insert(j);
//cout<<t.top()<<" "<<j<<'\n';
}
t.push(j);
}
}
for1(i,1,m){
a[i][0]=inf;
stack<int>t;
t.push(0);
for1(j,1,n){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
if (t.top()!=0)b[i][j].insert(t.top());
t.push(j);
}
}
for1(i,1,m){
st[i].resz(n);
for1(j,1,n){
st[i].update(1,1,n,j,down[i][j],up[i][j]);
}
}
}
long long count_rectangles(vector<vector<int>>a1){
m=a1.size();
for1(i,0,m-1){
n=a1[i].size();
for1(j,0,n-1){
a[i+1][j+1]=a1[i][j];
}
}
//cout<<m<<" "<<n<<'\n';
build();
BIT bit;
bit.resz(m);
long long ans=0;
for1(i,2,m-1){
for1(j,1,n){
vector<int>num;
for (auto v:b[i][j])num.pb(v);
for (auto v:num){
int p=i;
for1(k,i,m-1){
if (b[k][j].find(v)!=b[k][j].end()){
p=k;
}
else break;
}
for1(k,i,p){
b[k][j].erase(v);
}
if (j-v+1-2<=0)continue;
//ans=0;
//cout<<v+1<<" "<<j-1<<" "<<i<<" "<<p<<'\n';
for2(k,p,i){
int vdcot=st[k+1].getmax(1,1,n,v+1,j-1);
vdcot=max(vdcot+1,i);
//cout<<vdcot<<" "<<k<<'\n';
if (vdcot<=k){
bit.add(k,1);
del[vdcot].pb(k);
}
int maxcot=st[k-1].getmin(1,1,n,v+1,j-1)-1;
maxcot=min(maxcot,p);
//cout<<k<<" "<<i<<" "<<maxcot<<'\n';
//cout<<down[k-1][v+1]<<'\n';
//ans=0;
if (maxcot>=i)ans+=1ll*bit.get(i,maxcot);
//cout<<k<<" "<<ans<<'\n';
for (auto v1:del[k]){
bit.add(v1,-1);
}
del[k].clear();
}
//cout<<ans<<" "<<v+1<<" "<<j-1<<" "<<i<<" "<<p<<'\n';
}
}
}
//cout<<ans<<'\n';
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen(".OUT","w",stdout);
int n1, m1;
cin>>n1>>m1;
vector<vector<int>> a1(n1, vector<int>(m1));
for (int i = 0; i < n1; i++) {
for (int j = 0; j < m1; j++) {
cin>>a1[i][j];
}
}
long long result = count_rectangles(a1);
printf("%lld\n", result);
return 0;
}*/
