#include<bits/stdc++.h>
#define MAXN 707
using namespace std;
int n,m,prow[MAXN][MAXN],nrow[MAXN][MAXN],l,r;
int pcol[MAXN][MAXN],ncol[MAXN][MAXN],br;
stack<int> st;
vector<int> lens[MAXN][MAXN];
int a[MAXN][MAXN],ans,cnt[MAXN][MAXN],last[MAXN][MAXN];
bool eq[MAXN][MAXN],qe[MAXN][MAXN];
void calc_intervals(){
for(int i=1;i<=n;i++){
while(!st.empty())st.pop();
for(int f=1;f<=m;f++){
while(!st.empty() and a[i][f]>=a[i][st.top()]){
if(a[i][f]==a[i][st.top()])eq[i][f]=true;
st.pop();
}
if(!st.empty())prow[i][f]=st.top();
st.push(f);
}
while(!st.empty())st.pop();
for(int f=m;f>=1;f--){
while(!st.empty() and a[i][f]>=a[i][st.top()]){
st.pop();
}
if(!st.empty())nrow[i][f]=st.top();
st.push(f);
}
}
for(int f=1;f<=m;f++){
while(!st.empty())st.pop();
for(int i=1;i<=n;i++){
while(!st.empty() and a[i][f]>=a[st.top()][f]){
if(a[i][f]==a[st.top()][f])qe[i][f]=true;
st.pop();
}
if(!st.empty())pcol[i][f]=st.top();
st.push(i);
}
while(!st.empty())st.pop();
for(int i=n;i>=1;i--){
while(!st.empty() and a[i][f]>=a[st.top()][f]){
st.pop();
}
if(!st.empty())ncol[i][f]=st.top();
st.push(i);
}
for(int i=1;i<=n;i++){
if(!qe[i][f] and ncol[i][f]<=n and pcol[i][f]>=1){
lens[ncol[i][f]-1][f].push_back(ncol[i][f]-pcol[i][f]-1);
}
}
}
}
bool ok(int x,int y,int l){
for(int i:lens[x][y]){
if(i==l)return true;
}
return false;
}
bool okrow(int w,int l,int r){
int maxs=0;
for(int i=l;i<=r;i++){
maxs=max(maxs,a[w][i]);
}
return maxs<a[w][l-1] and maxs<a[w][r+1];
}
long long count_rectangles(vector< vector<int> > A){
n=int(A.size()); m=int(A[0].size());
for(int i=1;i<=n;i++){
for(int f=1;f<=m;f++){
a[i][f]=A[i-1][f-1];
pcol[i][f]=prow[i][f]=0;
ncol[i][f]=nrow[i][f]=max(n,m)+1;
}
}
calc_intervals();
for(int i=2;i<=m-1;i++){
for(int f=i;f<=m-1;f++){
last[i][f]=1;
}
}
for(int i=2;i<=n-1;i++){
for(int f=2;f<=m-1;f++){
l=prow[i][f]+1; r=nrow[i][f]-1;
if(l<2 or r>m-1 or eq[i][f])continue;
if(last[l][r]==i-1)cnt[l][r]++;
else cnt[l][r]=1;
last[l][r]=i;
}
for(int f=2;f<=m-1;f++){
l=prow[i][f]+1; r=nrow[i][f]-1;
if(l<2 or r>m-1 or eq[i][f])continue;
for(int k:lens[i][r]){
if(k>cnt[l][r])continue;
for(int p=l;p<=r;p++){
if(!ok(i,p,k))break;
else if(p==r)ans++;
}
}
}
}
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}})<<"\n";
return 0;
}
*/
