#include <vector>
#include <iostream>
using namespace std;
struct SegmentTree
{
int mx=0;
int s,e;
SegmentTree* next[2];
SegmentTree(int l,int r)
{
s=l;
e=r;
if(s!=e)
{
int mid=(s+e)/2;
next[0]=new SegmentTree(s,mid);
next[1]=new SegmentTree(mid+1,e);
}
}
void insert(int l,int val)
{
if(e<l or l<s)
return;
mx=max(mx,val);
if(s==e)
return;
next[0]->insert(l,val);
next[1]->insert(l,val);
}
int get(int l,int r)
{
if(e<l or r<s)
return 0;
if(l<=s and e<=r)
return mx;
return max(next[0]->get(l,r),next[1]->get(l,r));
}
};
long long count_rectangles(std::vector<std::vector<int> >a)
{
long long ans=0;
int n=a.size();
int m=a[0].size();
SegmentTree* fix1[n-1];
SegmentTree* fix2[m-1];
for(int i=1;i<=(n-2);i++)
{
fix1[i]=new SegmentTree(1,m-2);
for(int j=1;j<=(m-2);j++)
{
fix1[i]->insert(j,a[i][j]);
}
}
for(int j=1;j<=(m-2);j++)
{
fix2[j]=new SegmentTree(1,n-2);
for(int i=1;i<=(n-2);i++)
{
fix2[j]->insert(i,a[i][j]);
}
}
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 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]->get(c1,c2);
if(fp>=mi)
{
pos=0;
break;
}
}
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]->get(r1,r2);
if(fp>=mi)
{
pos=0;
break;
}
}
ans+=pos;
}
}
}
}
return ans;
}
