#include "rect.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define SZ(X) (int)X.size()
#define PB push_back
#define ALL(X) X.begin(),X.end()
#define RI(X) scanf("%d",&X)
#define RII(X,Y) scanf("%d%d",&X,&Y)
#define RIII(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define DRI(X) int X;scanf("%d",&X)
#define DRII(X,Y) int X,Y;scanf("%d%d",&X,&Y)
#define DRIII(X,Y,Z) int X,Y,Z;scanf("%d%d%d",&X,&Y,&Z)
#define MS0(X) memset(X,0,sizeof(X));
#define MS1(X) memset(X,-1,sizeof(X));
#define REP(I,N) for(int I=0;I<N;++I)
#define REPP(I,A,B) for(int I=A;I<B;++I)
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef pair<LL,LL> PLL;
int R,C;
int d[2509][2509];
vector<PII> LU[2509][2509];
vector<PII> UL[2509][2509];
long long count_rectangles(std::vector<std::vector<int> > a) {
R=SZ(a);C=SZ(a[0]);
REP(i,R)REP(j,C)d[i][j]=a[i][j];
REP(i,R){
stack<int> st;
REP(j,C){
while(st.size()&&(d[i][st.top()]<d[i][j])){//look for first left value >=!
st.pop();
}
if(st.size()){
int k = st.top();
if(j-k>=2){
if(i){
auto it = lower_bound(ALL(LU[i-1][j]),MP(k,0));
if(it!=LU[i-1][j].end()&&it->F==k) LU[i][j].PB(MP(k,it->S));
else LU[i][j].PB(MP(k,i));
}
else LU[i][j].PB(MP(k,i));
}
}
st.push(j);
}
while(SZ(st))st.pop();
for(int j=C-1;j>=0;j--){
while(st.size()&&d[i][st.top()]<d[i][j]){//look for first right value >=!
st.pop();
}
if(st.size()){
int k = st.top();
if(d[i][k]!=d[i][j] && k-j>=2){
if(i){
auto it = lower_bound(ALL(LU[i-1][k]),MP(j,0));
if(it!=LU[i-1][k].end()&&it->F==j) LU[i][k].PB(MP(j,it->S));
else LU[i][k].PB(MP(j,i));
}
else LU[i][k].PB(MP(j,i));
}
}
st.push(j);
}
REP(j,C)sort(ALL(LU[i][j]));
/*REP(j,C){
printf ("PRINTING square: %d, %d\n",i,j);
for(PII v:LU[i][j]){
printf("%d %d ",v.F,v.S);
}puts("");
}puts("");*/
}
REP(j,C){
stack<int> st;
REP(i,R){
while(st.size()&&d[st.top()][j]<d[i][j]){//look for first left value >=!
st.pop();
}
if(st.size()){
int k = st.top();
if(i-k>=2){
if(j){
auto it = lower_bound(ALL(UL[i][j-1]),MP(k,0));
if(it!=UL[i][j-1].end()&&it->F==k) UL[i][j].PB(MP(k,it->S));
else UL[i][j].PB(MP(k,j));
}
else UL[i][j].PB(MP(k,j));
}
}
st.push(i);
}
while(SZ(st))st.pop();
for(int i=R-1;i>=0;i--){
while(st.size()&&d[st.top()][j]<d[i][j]){//look for first right value >=!
st.pop();
}
if(st.size()){
int k = st.top();
if(d[k][j]!=d[i][j] && k-i>=2){
if(j){
auto it = lower_bound(ALL(UL[k][j-1]),MP(i,0));
if(it!=UL[k][j-1].end()&&it->F==i) UL[k][j].PB(MP(i,it->S));
else UL[k][j].PB(MP(i,j));
}
else UL[k][j].PB(MP(i,j));
}
}
st.push(i);
}
REP(i,R)sort(ALL(UL[i][j]));
}
int ans = 0;
REPP(i,1,R-1){
REPP(j,2,C){
for(PII luv:LU[i][j]){
for(int uli=UL[i+1][j-1].size()-1;uli>=0;uli--){
PII ulv=UL[i+1][j-1][uli];
if(ulv.F<luv.S-1)break;
ans += (ulv.S <= luv.F+1);
}
}
}
}
return ans;
}
