#include "rect.h"
#include <vector>
#include <iostream>
#include <map>
#include <set>
using namespace std;
#define ll long long
int const NM=2500*2500*+10;
struct comp
{
int sz,l,r,u,d;
};
int n,m;
comp rec[NM]={};
int par[NM]={};
int x[4];
int root(int n)
{
return (par[n]==n?n:(par[n]=root(par[n])));
}
comp comb(comp a,comp b)
{
comp c;
c.sz=a.sz+b.sz;
c.l=min(a.l,b.l);
c.r=max(a.r,b.r);
c.u=min(a.u,b.u);
c.d=max(a.d,b.d);
return c;
}
vector<int>vals;
bool valid(comp a)
{
if (a.l==0||a.u==0||a.d==n-1||a.r==m-1)
return 0;
ll lv=(a.d-a.u)+1,lh=(a.r-a.l)+1;
return ((lv*lh)==a.sz);
}
bool ma(int i,int j)
{
if (j<0||j>=n*m||vals[j]>vals[i])
return 0;
return 1;
}
bool merge(int u,int v)
{
u=root(u);
v=root(v);
if (u==v)
return 1;
rec[u]=comb(rec[u],rec[v]);
par[v]=u;
return valid(rec[u]);
}
long long count_rectangles(vector<vector<int>>a)
{
n=a.size(),m=a[0].size();
x[0]=m,x[1]=-m,x[2]=-1,x[3]=1;
map<int,vector<int>>ind;
set<int>s;
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
vals.push_back(a[i][j]);
int nm=i*m+j;
par[nm]=nm;
rec[nm].sz=1;
rec[nm].l=rec[nm].r=j;
rec[nm].u=rec[nm].d=i;
s.insert(a[i][j]);
ind[a[i][j]].push_back(nm);
}
}
long long ans=0;
for (auto i:s)
{
set<int>g;
for (auto j:ind[i])
{
for (auto k:x)
{
if (ma(j,j+k))
{
merge(j,j+k);
}
}
g.insert(root(j));
}
for (auto i:g)
{
if (i!=root(i)||!valid(rec[i]))
continue;
// cout<<i<<endl;
ans++;
}
}
return ans;
}
