#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=2007,pot=1<<11;
set<int>V[N][N];
int U[N][2*pot+7];
int D[N][2*pot+7];
int n,m;
int queU(int v,int a,int b,int l,int r,int i)
{
if(a<=l&&b>=r) return U[i][v];
if(r<a||l>b) return -1;
return max(queU(2*v,a,b,l,(l+r)/2,i),queU(2*v+1,a,b,(l+r)/2+1,r,i));
}
int queD(int v,int a,int b,int l,int r,int i)
{
if(a<=l&&b>=r) return D[i][v];
if(r<a||l>b) return n;
return min(queD(2*v,a,b,l,(l+r)/2,i),queD(2*v+1,a,b,(l+r)/2+1,r,i));
}
ll count_rectangles(vector<vector<int>>a)
{
ll ans=0;
n=sz(a),m=sz(a[0]);
for(int i=1;i<n-1;i++)
{
deque<pair<int,int>>Q;
Q.pb({a[i][0],0});
for(int j=1;j<m;j++)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) V[Q.back().nd+1][j-1].insert(i);
Q.pb({a[i][j],j});
}
Q.clear();
Q.pb({a[i][m-1],m-1});
for(int j=m-2;j>=0;j--)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) V[j+1][Q.back().nd-1].insert(i);
Q.pb({a[i][j],j});
}
}
for(int i=0;i<n;i++)
{
for(int j=1;j<2*pot;j++)
{
U[i][j]=-1;
D[i][j]=n;
}
}
for(int j=0;j<m;j++)
{
deque<pair<int,int>>Q;
Q.pb({a[0][j],0});
for(int i=1;i<n;i++)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) U[i][j+pot]=Q.back().nd;
Q.pb({a[i][j],i});
}
Q.clear();
Q.pb({a[n-1][j],n-1});
for(int i=n-2;i>=0;i--)
{
while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
if(sz(Q)>0) D[i][j+pot]=Q.back().nd;;
Q.pb({a[i][j],i});
}
}
for(int i=0;i<n;i++)
{
for(int j=pot-1;j>0;j--)
{
U[i][j]=max(U[i][2*j],U[i][2*j+1]);
D[i][j]=min(D[i][2*j],D[i][2*j+1]);
}
}
for(int i=0;i<m;i++)
{
for(int j=i;j<m;j++)
{
//cout<<i<<" "<<j<<endl;
int p=0,l=-1;
for(auto x:V[i][j])
{
if(x!=l+1) p=x;
l=x;
for(int y=p;y<=x;y++)
{
// cout<<i<<" "<<j<<" "<<y<<" "<<x<<" "<<queD(1,i+1,j+1,1,pot,y-1)<<" "<<queU(1,i+1,j+1,1,pot,x+1)<<endl;
if(queD(1,i+1,j+1,1,pot,y-1)>x&&queU(1,i+1,j+1,1,pot,x+1)<y)
{
//cout<<"TAK"<<endl;
ans++;
}
}
//cout<<"Xd "<<p<<" "<<x<<endl;
//cout<<x<<endl;
}
//cout<<ans<<endl;
}
}
return ans;
}
/*
int main()
{
cout<<count_rectangles({
{4, 8, 7, 5, 6},
{7, 4, 10, 3, 5},
{9, 7, 20, 14, 2},
{9, 14, 7, 3, 6},
{5, 7, 5, 2, 7},
{4, 5, 13, 5, 6}})<<endl;
return 0;
}*/
