#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll lg[1000005];
struct Sparse_Table_Max{
// vector<vector<int> >stmax;
int stmax[2501][12];
// vector<ll>arr;
int arr[2501];
void init(ll n){
// stmax.resize(n+5);
// for(int i=0;i<n+5;i++){
// stmax[i].resize(12);
// }
// arr.resize(n+5);
}
void build(ll n){
for(int i=1;i<=n;i++){
stmax[i][0]=arr[i];
}
for(int j=1;j<=11;j++){
for(int i=1;i<=n;i++){
if(i+(1<<(j-1))<=n){
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
}
}
}
}
ll qry(ll ql, ll qr){
ll rng=lg[qr-ql+1];
return max(stmax[ql][rng],stmax[qr-(1<<rng)+1][rng]);
}
};
struct Sparse_Table_Min{
int stmin[2501][12];
int arr[2501];
void init(ll n){
}
void build(ll n){
for(int i=1;i<=n;i++){
stmin[i][0]=arr[i];
}
for(int j=1;j<=11;j++){
for(int i=1;i<=n;i++){
if(i+(1<<(j-1))<=n){
stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}
}
}
}
ll qry(ll ql, ll qr){
ll rng=lg[qr-ql+1];
return min(stmin[ql][rng],stmin[qr-(1<<rng)+1][rng]);
}
};
struct Fenwick{
vector<int>tree;
void init(ll n){
tree.resize(n+5,0);
}
void upd(ll n, ll m, ll val){
for(int i=n;i<=m;i+=(i&(-i))){
tree[i]+=val;
}
}
void reset(ll n, ll m){
for(int i=n;i<=m;i+=(i&(-i))){
tree[i]=0;
}
}
ll sum(ll e){
ll s=0;
while(e>=1){
s+=tree[e]; e-=(e&(-e));
}
return s;
}
ll qry(ll ql, ll qr){
return sum(qr)-sum(ql-1);
}
}BIT;
struct Union_Find{
vector<int>fa,siz,lef,righ;
void init(ll n){
fa.resize(n+5),siz.resize(n+5);
lef.resize(n+5),righ.resize(n+5);
for(int i=1;i<=n;i++){
fa[i]=i,siz[i]=1,lef[i]=righ[i]=i;
}
}
ll root(ll x){
if(fa[x]==x)return x;
return fa[x]=root(fa[x]);
}
void unite(ll u, ll v){
u=root(u),v=root(v);
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v],fa[v]=u;
lef[u]=min(lef[u],lef[v]);righ[u]=max(righ[u],righ[v]);
}
void clear(){
lef.clear(),righ.clear(),siz.clear(),fa.clear();
}
}dsu;
Sparse_Table_Min spmin[2505];
Sparse_Table_Max spmax[2505];
ll n,m;
int grid[2505][2505];
int maxi[2505][2505],mini[2505][2505];
vector<pair<int,int> >ope[2505];
vector<int>ele[2505];
vector<pair<int,int> >hv[2505];
vector<pair<int,int> >all;
vector<int>inside[10000005];
void proc(ll id){
vector<ll>srt;
for(int i=1;i<=m;i++){
srt.push_back(grid[id][i]);
}
sort(srt.begin(),srt.end());
srt.erase(unique(srt.begin(),srt.end()),srt.end());
for(int i=1;i<=m;i++){
ll it=lower_bound(srt.begin(),srt.end(),grid[id][i])-srt.begin()+1;
ele[it].push_back(i);
}
vector<pair<int,int> >ss;
dsu.init(m);
bool merged[m+5];
for(int i=1;i<=m;i++)merged[i]=0;
for(int i=1;i<=srt.size();i++){
for(auto& u: ele[i]){
if(u!=1){
if(merged[u-1])dsu.unite(u,u-1);
}
if(u!=m){
if(merged[u+1])dsu.unite(u,u+1);
}
merged[u]=1;
}
for(auto& u: ele[i]){
ll f=dsu.root(u);
ll l=dsu.lef[f],r=dsu.righ[f];
if(l!=1&&r!=m){
ss.push_back({l,r});
}
}
}
sort(ss.begin(),ss.end());
ss.erase(unique(ss.begin(),ss.end()),ss.end());
for(int i=1;i<=srt.size();i++)ele[i].clear();
dsu.clear();
hv[id]=ss;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=a.size(),m=a[0].size();
for(int i=2;i<=1000000;i*=2){
lg[i]=1;
}
for(int i=3;i<=1000000;i++){
lg[i]+=lg[i-1];
}
if(n<=2||m<=2)return 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
grid[i+1][j+1]=a[i][j];
}
}
for(int i=2;i<n;i++){
proc(i);
}
stack<pair<ll,ll> >sta;
for(int j=2;j<m;j++){
for(int i=1;i<=n;i++){
if(sta.size()==0){
sta.push({grid[i][j],i});
}
else{
while(sta.size()){
ll lol=sta.top().first;
if(lol<=grid[i][j]){
maxi[sta.top().second][j]=i-1;
sta.pop();
}
else{
break;
}
}
sta.push({grid[i][j],i});
}
}
while(sta.size()){
maxi[sta.top().second][j]=10000;
sta.pop();
}
}
for(int j=2;j<m;j++){
for(int i=n;i>=1;i--){
if(sta.size()==0){
sta.push({grid[i][j],i});
}
else{
while(sta.size()){
ll lol=sta.top().first;
if(lol<=grid[i][j]){
mini[sta.top().second][j]=i+1;
sta.pop();
}
else{
break;
}
}
sta.push({grid[i][j],i});
}
}
while(sta.size()){
mini[sta.top().second][j]=-10000;
sta.pop();
}
}
for(int i=1;i<=n;i++){
for(auto& u: hv[i]){
all.push_back(u);
}
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i=1;i<=n;i++){
spmin[i].init(m),spmax[i].init(m);
for(int j=1;j<=m;j++){
spmin[i].arr[j]=maxi[i][j];
spmax[i].arr[j]=mini[i][j];
}
spmin[i].build(m),spmax[i].build(m);
}
for(int i=1;i<=n;i++){
for(auto& u: hv[i]){
ll hsh=lower_bound(all.begin(),all.end(),u)-all.begin()+1;
inside[hsh].push_back(i);
}
}
ll answer=0;
BIT.init(n);
ll tot=all.size();
for(int i=1;i<=tot;i++){
// cout<<all[i-1].first<<" "<<all[i-1].second<<":\n";
ll lef=-1;
vector<pair<int,int> >po;
for(int j=0;j<inside[i].size();j++){
// cout<<inside[i][j]<<'\n';
if(j==0)lef=inside[i][j];
else{
if(inside[i][j]!=inside[i][j-1]+1){
po.push_back({lef,inside[i][j-1]});
lef=inside[i][j];
}
}
}
po.push_back({lef,inside[i][inside[i].size()-1]});
for(auto& [l,r]: po){
// cout<<l<<" "<<r<<'\n';
for(int j=l-1;j<=r-1;j++){
ope[j+1].push_back({j,1});
ll nxt=spmin[j].qry(all[i-1].first,all[i-1].second)+1;
if(nxt<=r){
ope[nxt].push_back({j,-1});
}
}
for(int j=l;j<=r;j++){
for(auto& k: ope[j]){
// cout<<"operation "<<k.first<<" "<<k.second<<'\n';
if(k.second==1)BIT.upd(k.first,n,1);
else BIT.upd(k.first,n,-1);
}
ll go=spmax[j+1].qry(all[i-1].first,all[i-1].second);
go--;
go=max(go,1LL);
answer+=BIT.qry(go,j-1);
}
for(int j=l-1;j<=r;j++)BIT.reset(j,n),ope[j].clear();
// cout<<answer<<'\n';
}
}
return answer;
// return -1;
}
