#include <vector>
#include <iostream>
using namespace std;
long long count_rectangles(std::vector<std::vector<int> >a)
{
long long ans=0;
int n=a.size();
int m=a[0].size();
int fix1[n][m][m];
for(int i=1;i<=(n-2);i++)
{
for(int j=1;j<=(m-2);j++)
{
fix1[i][j][j]=a[i][j];
int j1=j+1;
while(j1<=(m-2))
{
fix1[i][j][j1]=max(a[i][j1],fix1[i][j][j1-1]);
j1++;
}
}
}
int fix2[m][n][n];
for(int i=1;i<=(m-2);i++)
{
for(int j=1;j<=(n-2);j++)
{
fix2[i][j][j]=a[j][i];
int j1=j+1;
while(j1<=(n-2))
{
fix2[i][j][j1]=max(a[j1][i],fix2[i][j][j1-1]);
j1++;
}
}
}
for(int r1=1;r1<=(n-2);r1++)
{
for(int c1=1;c1<=(m-2);c1++)
{
for(int r2=r1;r2<=(n-2);r2++)
{
for(int c2=c1;c2<=(m-2);c2++)
{
bool pos=1;
for(int addj=0;addj<=(c2-c1);addj++)
{
int cellj=c1+addj;
int mi=min(a[r1-1][cellj],a[r2+1][cellj]);
int fp=fix2[cellj][r1][r2];
if(fp>=mi)
{
// if(r1==1 and c1==1 and r2==2 and c2==1)
// {
// cout<<"Hell "<<mi<<endl;
// cout<<fp<<endl;
// }
pos=0;
break;
}
}
for(int addi=0;addi<=(r2-r1) and pos;addi++)
{
int celli=r1+addi;
int mi=min(a[celli][c1-1],a[celli][c2+1]);
int fp=fix1[celli][c1][c2];
if(fp>=mi)
{
// if(r1==1 and c1==1 and r2==2 and c2==1)
// {
// cout<<"Hell "<<mi<<endl;
// cout<<fp<<endl;
// cout<<celli<<endl;
// }
pos=0;
break;
}
}
// if(pos)
// {
// cout<<"Hello "<<r1<<' '<<c1<<' '<<r2<<' '<<c2<<' '<<pos<<endl;
// }
ans+=pos;
}
}
}
}
return ans;
}
