#include"rect.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
#define N 2500
#define H 3
int h,w,d[N][N];
namespace rangemax{
int dat1[H][N][N];//dat1[x][y1][y2]
int dat2[N][H][H];//dat2[y][x1][x2]
ll max_x(ll x,ll y1,ll y2){
return dat1[x][y1][y2];
}
ll max_y(ll y,ll x1,ll x2){
return dat2[y][x1][x2];
}
void init(){
rep(i,h){
rep(l,w){
dat1[i][l][l]=d[i][l];
for(int r=l+1;r<w;r++){
dat1[i][l][r]=max(dat1[i][l][r-1],d[i][r]);
}
}
}
rep(i,w){
rep(l,h){
dat2[i][l][l]=d[l][i];
for(int r=l+1;r<h;r++){
dat2[i][l][r]=max(dat2[i][l][r-1],d[r][i]);
}
}
}
}
};
namespace rangejudge{
int dat1[H][N][N];//dat1[x][y1][y2]
int dat2[N][H][H];//dat2[y][x1][x2]
void init(){
rep(i,h){
for(int l=0;l<w;l++)for(int r=l;r<w;r++){
dat1[i][l][r]=rangemax::max_x(i,l,r)>=min(d[i][l-1],d[i][r+1]);
}
}
for(int l=0;l<w;l++)for(int r=l;r<w;r++){
for(int i=1;i<h;i++)dat1[i][l][r]+=dat1[i-1][l][r];
}
rep(i,w){
for(int l=0;l<h;l++)for(int r=l;r<h;r++){
dat2[i][l][r]=rangemax::max_y(i,l,r)>=min(d[l-1][i],d[r+1][i]);
}
}
for(int l=0;l<h;l++)for(int r=l;r<h;r++){
for(int i=1;i<w;i++)dat2[i][l][r]+=dat2[i-1][l][r];
}
}
bool solve(ll x1,ll x2,ll y1,ll y2){
if(dat1[x2][y1][y2]-dat1[x1-1][y1][y2]>0)return 0;
if(dat2[y2][x1][x2]-dat2[y1-1][x1][x2]>0)return 0;
return 1;
}
};
ll count_rectangles(vector<vector<int> >A){
h=A.size(),w=A[0].size();
rep(i,h)rep(j,w)d[i][j]=A[i][j];
rangemax::init();
rangejudge::init();
ll ans=0;
for(int x1=1;x1<h-1;x1++)for(int x2=x1;x2<h-1;x2++)
for(int y1=1;y1<w-1;y1++)for(int y2=y1;y2<w-1;y2++){
ans+=rangejudge::solve(x1,x2,y1,y2);
}
return ans;
}/*
int main(){
ll h,w;
cin>>h>>w;
vector<vector<int> >a(h);
rep(i,h){
rep(j,w){
ll val;cin>>val;
a[i].push_back(val);
}
}
cout<<count_rectangles(a)<<endl;
}*/
