#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];
int check(int aa,int bb,int cc,int ee){
/*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;
}
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;
}
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=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;
}
