#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 dsux(n*m);
DSU dsuy(n*m);
vector<bool> used(n*m);
vector<vector<pair<int,int>>> opx(n);
vector<vector<pair<int,int>>> opy(n);
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;
dsux.go(x*m+y,x,y);
dsuy.go(x*m+y,x,y);
active[x][y]=true;
for(int k=0;k<2;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;
dsuy.unite(x*m+y,nx*m+ny);
}
for(int k=2;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;
dsux.unite(x*m+y,nx*m+ny);
}
st.push_back(x*m+y);
pos++;
}
{
vector<int> st2;
for(auto v:st){
int i=dsux.find(v);
if(used[i]) continue;
used[i]=true;
st2.push_back(i);
int x1=dsux.mnx[i]-1;
int x2=dsux.mxx[i]+1;
int y=v%m;
if(x1>=0 and x1<n and x2>=0 and x2<n){
//cout<<"x "<<y+1<<' '<<x1+1<<' '<<x2+1<<'\n';
opx[x1].push_back({x2,y});
}
}
for(auto v:st2){
used[v]=false;
}
}
{
vector<int> st2;
for(auto v:st){
int i=dsuy.find(v);
if(used[i]) continue;
used[i]=true;
st2.push_back(i);
int y1=dsuy.mny[i]-1;
int y2=dsuy.mxy[i]+1;
int x=v/m;
if(y1>=0 and y1<m and y2>=0 and y2<m){
//cout<<"y "<<x+1<<' '<<y1+1<<' '<<y2+1<<'\n';
opy[x].push_back({y1,y2});
}
}
for(auto v:st2){
used[v]=false;
}
}
}
ll ans=0;
for(int x1=0;x1<n;x1++){
sort(all(opx[x1]));
int pos=0;
vector<vector<int>> cnt(m,vector<int>(m));
for(int x2=x1+2;x2<n;x2++){
vector<int> pre(m);
while(pos<(int)opx[x1].size() and opx[x1][pos].f==x2){
pre[opx[x1][pos].s]++;
pos++;
}
for(int i=1;i<m;i++){
pre[i]+=pre[i-1];
}
for(auto [y1,y2]:opy[x2-1]){
cnt[y1][y2]++;
if(cnt[y1][y2]==(x2-x1-1)){
if(pre[y2-1]-pre[y1]==(y2-y1-1)){
//cout<<x1+1<<' '<<x2+1<<' '<<y1+1<<' '<<y2+1<<'\n';
ans++;
}
}
}
}
}
return ans;
}
