#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define fi first
#define se second
#define each(i,x) for(auto i:x)
using ll=long long;
/*
#include "grader.cpp"
/**/
template<class T,auto op,auto e>
struct SegTree{
vector<T> val;
int n;
SegTree(int sz){
n=sz;
val.resize(n*2,e());
}
void set(int p,T v){
p+=n;
val[p]=v;
while(p>1){
p/=2;
val[p]=op(val[p*2],val[p*2+1]);
}
}
T prod(int l,int r){
l+=n;
r+=n;
T rl=e(),rr=e();
while(l<r){
if(l&1){
rl=op(rl,val[l]);l++;
}
if(r&1){
r--;rr=op(val[r],rr);
}
l/=2;r/=2;
}
return op(rl,rr);
}
};
ll mn(ll x,ll y){return min(x,y);}
ll mx(ll x,ll y){return max(x,y);}
ll emn(){
return 1LL<<60;
}
ll emx(){
return -(1LL<<60);
}
using seg=pair<int,int>;
int num(seg sm){
return sm.fi*2502+sm.se;
}
ll rc_num(seg r,seg c){
return num(r)*998244353LL+num(c);
}
const int X=2510*2510;
long long count_rectangles(std::vector<std::vector<int> > a) {
int n=a.size();int m=a[0].size();
vector<vector<seg>> r(n,vector<seg>(m,{-1,-1}));
vector<vector<seg>> c(n,vector<seg>(m,{-1,-1}));
rep(i,n){
vector<pair<int,int>> pos(m);
rep(j,m){
pos[j]={a[i][j],j};
}
sort(all(pos)),reverse(all(pos));
SegTree<ll,mn,emn> rmq(m);
SegTree<ll,mx,emx> rMq(m);
int cnt=0;
rep(j,m){
while(pos[j].fi!=pos[cnt].fi){
rmq.set(pos[cnt].se,pos[cnt].se);
rMq.set(pos[cnt].se,pos[cnt].se);
cnt++;
}
ll lf=rMq.prod(0,pos[j].se);
ll ri=rmq.prod(pos[j].se,m);
if(lf<0||ri>m)continue;
r[i][pos[j].se]={lf+1,ri};
}
}
rep(i,m){
vector<pair<int,int>> pos(n);
rep(j,n){
pos[j]={a[j][i],j};
}
sort(all(pos)),reverse(all(pos));
SegTree<ll,mn,emn> rmq(n);
SegTree<ll,mx,emx> rMq(n);
int cnt=0;
rep(j,n){
while(pos[j].fi!=pos[cnt].fi){
rmq.set(pos[cnt].se,pos[cnt].se);
rMq.set(pos[cnt].se,pos[cnt].se);
cnt++;
}
ll lf=rMq.prod(0,pos[j].se);
ll ri=rmq.prod(pos[j].se,n);
if(lf<0||ri>n)continue;
c[pos[j].se][i]={lf+1,ri};
}
}
unordered_set<ll> cand;
vector<vector<int>> rr(X);
rep(i,n){
rep(j,m){
if(r[i][j].fi!=-1&&(rr[num(r[i][j])].empty()||rr[num(r[i][j])].back()!=i)){
rr[num(r[i][j])].push_back(i);
}
}
}
vector<vector<int>> cc(X);
rep(i,m){
rep(j,n){
if(c[j][i].fi!=-1&&(cc[num(c[j][i])].empty()||cc[num(c[j][i])].back()!=i)){
cc[num(c[j][i])].push_back(i);
}
}
}
ll ret=0;
rep(i,n){
rep(j,m){
if(r[i][j].fi!=-1&&c[i][j].fi!=-1){
ll nm=rc_num(r[i][j],c[i][j]);
if(!cand.count(nm)){
cand.insert(nm);
int m1=lower_bound(all(cc[num(c[i][j])]),r[i][j].fi)-cc[num(c[i][j])].begin();
int m2=lower_bound(all(cc[num(c[i][j])]),r[i][j].se)-cc[num(c[i][j])].begin();
if(r[i][j].se-r[i][j].fi!=m2-m1)continue;
m1=lower_bound(all(rr[num(r[i][j])]),c[i][j].fi)-rr[num(r[i][j])].begin();
m2=lower_bound(all(rr[num(r[i][j])]),c[i][j].se)-rr[num(r[i][j])].begin();
if(c[i][j].se-c[i][j].fi!=m2-m1)continue;
ret++;
}
}
}
}
/*
*/
return ret;
}
