#include "rect.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
namespace{
struct DSU{
vector<int> e;
vector<int> mnx,mny,mxx,mxy;
DSU(int n){
e=vector<int>(n,-1);
mnx=mny=mxx=mxy=vector<int>(n);
}
void go(int i,int x,int y){
mnx[i]=mxx[i]=x;
mny[i]=mxy[i]=y;
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
mnx[a]=min(mnx[a],mnx[b]);
mny[a]=min(mny[a],mny[b]);
mxx[a]=max(mxx[a],mxx[b]);
mxy[a]=max(mxy[a],mxy[b]);
return true;
}
};
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n=(int)a.size();
int m=(int)a[0].size();
vector<pair<int,pair<int,int>>> vec;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
vec.push_back({a[i][j],{i,j}});
}
}
sort(all(vec));
vector<vector<bool>> active(n,vector<bool>(m));
DSU dsu(n*m);
vector<bool> used(n*m);
ll ans=0;
auto ok=[&](int i){
ll sz=-dsu.e[i];
ll sz2=1ll*(dsu.mxx[i]-dsu.mnx[i]+1)*(dsu.mxy[i]-dsu.mny[i]+1);
return (sz==sz2 and dsu.mnx[i]!=0 and dsu.mxx[i]!=n-1 and dsu.mny[i]!=0 and dsu.mxy[i]!=m-1);
};
for(int pos=0;pos<n*m;){
int cur=vec[pos].f;
vector<int> st;
while(pos<n*m and vec[pos].f==cur){
auto [x,y]=vec[pos].s;
dsu.go(x*m+y,x,y);
active[x][y]=true;
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx<0 or nx>=n or ny<0 or ny>=m or !active[nx][ny]) continue;
dsu.unite(x*m+y,nx*m+ny);
}
st.push_back(x*m+y);
pos++;
}
vector<int> st2;
for(auto v:st){
int i=dsu.find(v);
if(used[i]) continue;
used[i]=true;
st2.push_back(i);
if(ok(i)){
//cout<<cur<<' '<<i/m+1<<' '<<i%m+1<<'\n';
ans++;
}
}
for(auto v:st2){
used[v]=false;
}
}
return ans;
}
