#include "rect.h"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
bool dv[707][707][707],dh[707][707][707];
long long count_rectangles(std::vector<std::vector<int> > a)
{
int n=a.size(),m=a[0].size();
for(int i=0;i<n;i++)
{
stack<int> st;
for(int j=0;j<m;j++)
{
while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
if(!st.empty()) dv[i][st.top()+1][j-1]=true;
st.push(j);
}
while(!st.empty()) st.pop();
for(int j=m-1;j>=0;j--)
{
while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
if(!st.empty()) dv[i][j+1][st.top()-1]=true;
st.push(j);
}
}
for(int i=0;i<m;i++)
{
stack<int> st;
for(int j=0;j<n;j++)
{
while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
if(!st.empty()) dh[st.top()+1][j-1][i]=true;
st.push(j);
}
while(!st.empty()) st.pop();
for(int j=n-1;j>=0;j--)
{
while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
if(!st.empty()) dh[j+1][st.top()-1][i]=true;
st.push(j);
}
}
long long sol=0;
for(int a=1;a<n;a++) for(int b=a+1;b<n;b++) for(int c=1;c<m;c++) for(int d=c+1;d<m;d++)
{
if(!dh[a][b-1][d-1]) break;
bool fas=false;
for(int i=a;i<b && !fas;i++) if(!dv[i][c][d-1]) fas=true;
if(!fas) sol++;
}
return sol;
}
