#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)
{
//printf("%d %d %d %d\n",x,y,sx,sy);
if(have[x][y]) return ;
if(tt[x][y]==tt[sx][sy]) sa.push_back(make_pair(sx,sy));
//printf("bb %d %d\n",x,y);
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!=-1&&(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!=-1&&(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,now=0;
tt=all;
N=all.size();
M=all[0].size();
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
how[now].x=i;
how[now].y=j;
how[now].con=all[i][j];
now++;
}
}
sort(how,how+N*M,cmp);
for(i=0;i<N*M;i++)
{
printf("%d %d %d\n",i,how[i].x,how[i].y);
if(!have[how[i].x][how[i].y])
{
printf("aa\n");
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++)
{
//printf("%d %d %d %d %d %d %d\n",i,j,l[i][j],r[i][j],u[i][j],d[i][j],con[i][j]);
if((r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1)==con[i][j]&&l[i][j]!=0&&r[i][j]!=M-1&&u[i][j]!=0&&d[i][j]!=N-1) 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();
}
