#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
pair<int,int> dsu[2510][2510];
int sz[2510][2510],nl[2510][2510],xr[2510][2510],nu[2510][2510],xd[2510][2510],use[2510][2510],mp[2510][2510],n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
ll ans;
pair<int,int> f(pair<int,int> p){
auto [x,y]=p;
if(dsu[x][y]==p){
return p;
}else{
dsu[x][y]=f(dsu[x][y]);
}
return dsu[x][y];
}
bool onion(pair<int,int> p1,pair<int,int> p2){
p1=f(p1);
p2=f(p2);
if(p1==p2)return 0;
auto [x1,y1]=p1;
auto [x2,y2]=p2;
if(sz[x1][y1]>sz[x2][y2])swap(p1,p2),swap(x1,x2),swap(y1,y2);
dsu[x1][y1]=dsu[x2][y2];
sz[x2][y2]+=sz[x1][y1];
nl[x2][y2]=min(nl[x1][y1],nl[x2][y2]);
xr[x2][y2]=max(xr[x1][y1],xr[x2][y2]);
nu[x2][y2]=min(nu[x1][y1],nu[x2][y2]);
xd[x2][y2]=max(xd[x1][y1],xd[x2][y2]);
return 1;
}
ll count_rectangles(vector<vector<int>> a) {
n=a.size();
m=a[0].size();
ans=0;
vector<pair<int,pair<int,int>>> pt;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
mp[i][j]=a[i-1][j-1];
dsu[i][j]={i,j};
sz[i][j]=1;
nl[i][j]=j;
xr[i][j]=j;
nu[i][j]=i;
xd[i][j]=i;
pt.push_back({mp[i][j],{i,j}});
}
}
sort(pt.begin(),pt.end());
pt.push_back({-1,{0,0}});
vector<pair<int,int>> god;
for(int i=0;i<n*m;i++){
if(pt[i].F!=pt[i+1].F){
for(auto &x:god){
x=f(x);
}
sort(god.begin(),god.end());
god.erase(unique(god.begin(),god.end()),god.end());
for(auto x:god){
auto [u,v]=x;
if(sz[u][v]==(xr[u][v]-nl[u][v]+1)*(xd[u][v]-nu[u][v]+1)
&&xr[u][v]!=m&&nl[u][v]!=1&&xd[u][v]!=n&&nu[u][v]!=1)ans++;
}
god.clear();
}
auto [x,y]=pt[i].S;
god.push_back({x,y});
use[x][y]=1;
for(int c=0;c<4;c++){
int nx=x+dx[c],ny=y+dy[c];
if(use[nx][ny]){
onion({x,y},{nx,ny});
}
}
}
return ans;
}
