#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
#include "rect.h"
vector<vector<int>> it;
int n,m;
int le[2501][2501];
int re[2501][2501];
int uu[2501][2501];
int dd[2501][2501];
vector<pair<int,int>> pre[2501][2501];
int check(int aa,int bb,int cc,int ee){
if(aa<=0 or aa>=n-1){
return 0;
}
if(cc<=0 and cc>=n-1){
return 0;
}
if(bb<=0 or bb>=m-1){
return 0;
}
if(ee<=0 and ee>=m-1){
return 0;
}
if(cc<aa or ee<bb){
return 0;
}
/*if(aa==1 and bb==1 and cc==1 and ee==1){
cout<<11<<endl;
cout<<re[1][bb-1]<<":"<<le[1][ee+1]<<endl;
}*/
for(int i=aa;i<=cc;i++){
int xx=min(it[i][bb-1],it[i][ee+1]);
if(xx==it[i][bb-1]){
if(re[i][bb-1]==ee+1){
continue;
}
}
if(xx==it[i][ee+1]){
if(le[i][ee+1]==bb-1){
continue;
}
}
return 0;
}
for(int i=bb;i<=ee;i++){
int xx=min(it[aa-1][i],it[cc+1][i]);
if(it[aa-1][i]==xx){
if(dd[aa-1][i]==cc+1){
continue;
}
}
if(xx==it[cc+1][i]){
if(uu[cc+1][i]==aa-1){
continue;
}
}
return 0;
}
//cout<<aa<<":"<<bb<<":"<<cc<<":"<<ee<<endl;
return 1;
}
llo count_rectangles(vector<vector<int>> ac) {
it=ac;
n=it.size();
m=it[0].size();
for(int i=0;i<n;i++){
vector<pair<int,int>> ss;
for(int j=0;j<m;j++){
while(ss.size()){
if(ss.back().a<it[i][j]){
ss.pop_back();
}
else{
break;
}
}
le[i][j]=-1;
if(ss.size()){
le[i][j]=ss.back().b;
pre[i][ss.back().b].pb({i,j});
}
ss.pb({it[i][j],j});
}
}
for(int i=0;i<n;i++){
vector<pair<int,int>> ss;
for(int j=m-1;j>=0;j--){
while(ss.size()){
if(ss.back().a<it[i][j]){
ss.pop_back();
}
else{
break;
}
}
re[i][j]=-1;
if(ss.size()){
if(ss.back().a!=it[i][j]){
re[i][j]=ss.back().b;
}
}
ss.pb({it[i][j],j});
}
}
/*for(int j=0;j<m;j++){
cout<<re[1][j]<<".";
}
cout<<endl;*/
for(int j=0;j<m;j++){
vector<pair<int,int>> ss;
for(int i=0;i<n;i++){
while(ss.size()){
if(ss.back().a<it[i][j]){
ss.pop_back();
}
else{
break;
}
}
uu[i][j]=-1;
if(ss.size()){
uu[i][j]=ss.back().b;
}
ss.pb({it[i][j],i});
}
}
for(int j=0;j<m;j++){
vector<pair<int,int>> ss;
for(int i=n-1;i>=0;i--){
while(ss.size()){
if(ss.back().a<it[i][j]){
ss.pop_back();
}
else{
break;
}
}
dd[i][j]=-1;
if(ss.size()){
if(ss.back().a!=it[i][j]){
dd[i][j]=ss.back().b;
}
}
ss.pb({it[i][j],i});
}
}
llo ans=0;
for(int i=0;i<n-2;i++){
for(int j=0;j<m-2;j++){
int aa,bb,cc,ee;
aa=i+1;
bb=j+1;
if(dd[i][j+1]>-1){
cc=dd[i][j+1]-1;
int st=1;
for(int k=bb;k<m-1;k++){
ee=k;
ans=(ans+check(aa,bb,cc,ee));
}
continue;
for(auto jj:pre[i+1][j]){
ee=jj.b-1;
if(aa<=cc and bb<=ee){
/*if(i==3 and j==2){
cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
}*/
ans=ans+check(aa,bb,cc,ee);
if(jj.b==re[i+1][j]){
st=0;
}
}
}
if(re[i+1][j]!=-1){
ee=re[i+1][j]-1;
if(aa<=cc and bb<=ee){
/*if(i==3 and j==2){
cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
}*/
ans=ans+check(aa,bb,cc,ee);
}
}
}
}
}
//cout<<11<<endl;
for(int i=n-1;i>1;i--){
for(int j=0;j<m-2;j++){
if(uu[i][j+1]>-1){
int aa,bb,cc,ee;
bb=j+1;
cc=i-1;
aa=uu[i][j+1]+1;
for(int k=bb;k<m-1;k++){
ee=k;
ans=(ans+check(aa,bb,cc,ee));
}
continue;
int st=1;
/* if(i==2 and j==0){
cout<<aa<<","<<bb<<","<<cc<<","<<endl;
}*/
for(auto jj:pre[aa][bb-1]){
ee=jj.b-1;
if(aa<=cc and bb<=ee){
/*if(i==2 and j==0){
cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
}*/
ans=ans+check(aa,bb,cc,ee);
if(jj.b==re[aa][cc-1]){
st=0;
}
}
}
if(re[aa][bb-1]!=-1){
ee=re[aa][bb-1]-1;
if(aa<=cc and bb<=ee){
/* if(i==2 and j==0){
cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
}*/
ans=ans+check(aa,bb,cc,ee);
}
}
}
}
}
/* for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
for(int k=i;k<n-1;k++){
for(int l=j;l<m-1;l++){
if(check(i,j,k,l)==1){
cout<<i<<":"<<j<<":"<<k<<":"<<l<<endl;
}
ans+=check(i,j,k,l);
}
}
}
}*/
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(re[i][j]>j+1){
}
}
}
*/
return ans;
}
