#include "rect.h"
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
int can1[205][205][205]={0};
int can2[205][205][205]={0};
bool have[2505][2505]={0};
int N,M;
int l[2505][2505];
int r[2505][2505];
int u[2505][2505];
int d[2505][2505];
int con[2505][2505]={0};
vector< vector<int> > tt;
vector < pair < int , int > > sa;
set < pair < pair < int , int > , pair < int ,int > > > can;
struct A
{
int x,y;
int con;
}how[2505*2505];
void F(int x,int y,int sx,int sy)
{
if(have[x][y]) return ;
if(tt[x][y]==tt[sx][sy]) sa.push_back(make_pair(sx,sy));
have[x][y]=1;
con[x][y]++;
l[x][y]=y;
r[x][y]=y;
u[x][y]=x;
d[x][y]=x;
if(y+1!=M&&(tt[x][y]>tt[x][y+1]||tt[x][y]==tt[x][y+1]&&!have[x][y+1]))
{
F(x,y+1,sx,sy);
l[x][y]=min(l[x][y],l[x][y+1]);
r[x][y]=max(r[x][y],r[x][y+1]);
u[x][y]=min(u[x][y],u[x][y+1]);
d[x][y]=max(d[x][y],d[x][y+1]);
con[x][y]+=con[x][y+1];
}
if(y-1!=0&&(tt[x][y]>tt[x][y-1]||tt[x][y]==tt[x][y-1]&&!have[x][y-1]))
{
F(x,y-1,sx,sy);
l[x][y]=min(l[x][y],l[x][y-1]);
r[x][y]=max(r[x][y],r[x][y-1]);
u[x][y]=min(u[x][y],u[x][y-1]);
d[x][y]=max(d[x][y],d[x][y-1]);
con[x][y]+=con[x][y-1];
}
if(x+1!=N&&(tt[x][y]>tt[x+1][y]||tt[x][y]==tt[x+1][y]&&!have[x+1][y]))
{
F(x+1,y,sx,sy);
l[x][y]=min(l[x][y],l[x+1][y]);
r[x][y]=max(r[x][y],r[x+1][y]);
u[x][y]=min(u[x][y],u[x+1][y]);
d[x][y]=max(d[x][y],d[x+1][y]);
con[x][y]+=con[x+1][y];
}
if(x-1!=0&&(tt[x][y]>tt[x-1][y]||tt[x][y]==tt[x-1][y]&&!have[x-1][y]))
{
F(x-1,y,sx,sy);
l[x][y]=min(l[x][y],l[x-1][y]);
r[x][y]=max(r[x][y],r[x-1][y]);
u[x][y]=min(u[x][y],u[x-1][y]);
d[x][y]=max(d[x][y],d[x-1][y]);
con[x][y]+=con[x-1][y];
}
}
bool cmp(A a,A b)
{
return a.con<b.con;
}
long long count_rectangles(vector< vector<int> > all)
{
int i,j,k,ll,m,n,big=0,ok,now=0;
long long ans=0;
N=all.size();
M=all[0].size();
tt=all;
if(N==3)
{
for(i=1;i<M-1;i++)
{
ok=1;
big=0;
for(j=i;j<M-1;j++)
{
if(all[1][j]>=all[0][j]||all[1][j]>=all[2][j]) ok=0;
big=max(big,all[1][j]);
if(ok&&big<min(all[1][i-1],all[1][j+1])) ans++;
}
}
return ans;
}
else if(N<3) return 0;
else if(max(N,M)<=200)
{
for(i=1;i<N;i++)
{
for(j=1;j<M;j++)
{
big=0;
for(k=j;k<M-1;k++)
{
big=max(big,all[i][k]);
if(big<all[i][j-1]&&big<all[i][k+1]) can1[i][j][k]=1;
can1[i][j][k]+=can1[i-1][j][k];
}
}
}
for(i=1;i<M;i++)
{
for(j=1;j<N;j++)
{
big=0;
for(k=j;k<N-1;k++)
{
big=max(big,all[k][i]);
if(big<all[j-1][i]&&big<all[k+1][i]) can2[i][j][k]=1;
can2[i][j][k]+=can2[i-1][j][k];
}
}
}
for(i=1;i<N-1;i++)
{
for(j=i;j<N-1;j++)
{
for(k=1;k<M-1;k++)
{
for(ll=k;ll<M-1;ll++)
{
if(can1[j][k][ll]-can1[i-1][k][ll]==j-i+1&&can2[ll][i][j]-can2[k-1][i][j]==ll-k+1) ans++;
}
}
}
}
}
else
{
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
how[now].x=i;
how[now].y=j;
now++;
}
}
sort(how,how+N*M,cmp);
for(i=0;i<N*M;i++)
{
if(!have[how[i].x][how[i].y])
{
sa.clear();
F(how[i].x,how[i].y,how[i].x,how[i].y);
for(auto j:sa)
{
l[j.first][j.second]=l[how[i].x][how[i].y];
r[j.first][j.second]=r[how[i].x][how[i].y];
u[j.first][j.second]=u[how[i].x][how[i].y];
d[j.first][j.second]=d[how[i].x][how[i].y];
con[j.first][j.second]=con[how[i].x][how[i].y];
}
}
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if((r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1)==con[i][j]) can.insert(make_pair(make_pair(l[i][j],r[i][j]),make_pair(u[i][j],d[i][j])));
}
}
return (long long) can.size();
}
return ans;
}
