#include "rect.h"
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int maxn=2510;
const int maxa=7e6+10;
int n,m;
vector<vector<int> > a;
int ul[maxn][maxn],ud[maxn][maxn];
vector<pii> ver[maxn];
int bit[maxn];
int stk=0;
int stek[maxn];
vector<int> bucket[maxn];
void add(int x,int t=1){
x++;
for(;x<maxn;x+=x&-x) bit[x]+=t;
}
int qry(int x){
int ret=0;
x++;
if(x==0) return 0;
for(;x>0;x-=x&-x) ret+=bit[x];
return ret;
}
int query(int l,int r){
return qry(r)-qry(l-1);
}
int res=0;
bool comp(tuple<int,int,int,int,int,int> &a,tuple<int,int,int,int,int,int> &b){
return get<4>(a)<get<4>(b);
}
bool comp2(tuple<int,int,int,int,int,int> &a,tuple<int,int,int,int,int,int> &b){
if(get<0>(a)<get<0>(b)) return true;
if(get<0>(a)>get<0>(b)) return false;
if(get<1>(a)<get<1>(b)) return true;
else return false;
}
ll count_rectangles(vector<vector<int> > _a){
swap(a,_a); n=a.size(); m=a[0].size();
for(int i=0;i<n;i++){
stk=0;
for(int j=0;j<m;j++){
while(stk>0 && a[i][stek[stk-1]]<a[i][j]) stk--;
if(stk==0) ul[i][j]=-1;
else ul[i][j]=stek[stk-1];
stek[stk++]=j;
if(ul[i][j]==j-1) ul[i][j]=-1;
} stk=0;
for(int j=m-1;j>=0;j--){
while(stk>0 && a[i][stek[stk-1]]<a[i][j]) stk--;
if(stk==0) ud[i][j]=-1;
else ud[i][j]=stek[stk-1];
stek[stk++]=j;
if(ud[i][j]==j+1) ud[i][j]=-1;
if(ud[i][j]!=-1 && a[i][j]==a[i][ud[i][j]]) ud[i][j]=-1;
} stk=0;
}
for(int i=0;i<m;i++){
for(int i=0;i<n;i++) bucket[i].clear();
for(int j=0;j<n;j++){
while(stk>0 && a[stek[stk-1]][i]<a[j][i]) stk--;
if(stk>0){bucket[stek[stk-1]].push_back(j);}
stek[stk++]=j;
} stk=0;
for(int j=n-1;j>=0;j--){
while(stk>0 && a[stek[stk-1]][i]<a[j][i]) stk--;
if(stk>0){bucket[j].push_back(stek[stk-1]);}
stek[stk++]=j;
} stk=0;
for(int j=0;j<n;j++) for(int k:bucket[j]) ver[i].push_back({j,k});
ver[i].resize(unique(ver[i].begin(),ver[i].end())-ver[i].begin());
}
bool prvi=true;
vector<tuple<int,int,int,int,int,int> > sr; //col, vr, u, d, koji, res
vector<tuple<int,int,int,int,int,int> > sl;
for(int _=0;_<2;_++){
int klkr=0,klkl=0;
// desni cosak
vector<tuple<int,int,int> > tren;
for(int j=1;j<m;j++){
vector<tuple<int,int,int> > novi;
for(pii x:ver[j]){
if(x.second-x.first==1) continue;
auto it=lower_bound(tren.begin(),tren.end(),tuple<int,int,int>(x.first,x.second,-1));
if(it==tren.end() || get<0>(*it)!=x.first || get<1>(*it)!=x.second) novi.push_back({x.first,x.second,j});
else novi.push_back({x.first,x.second,get<2>(*it)});
}
for(auto x:tren){
int u,d,r,l;
u=get<0>(x); d=get<1>(x); r=j; l=get<2>(x)-1;
if(ul[u+1][r]==-1) continue;
if(ul[u+1][r]<l) continue;
l=ul[u+1][r];
if(prvi){
sr.push_back({l,r,u+1,d-1,klkr++,-1});
sl.push_back({r,l,u+1,d-1,klkl++,-1});
continue;
}else if(get<5>(sr[klkr++])+get<5>(sl[klkl++])!=d-u-1) continue;
#ifdef DEBUG
cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n";
#endif
res++;
}
swap(tren,novi);
} tren.clear();
// levi cosak
for(int j=m-2;j>=0;j--){
vector<tuple<int,int,int> > novi;
for(pii x:ver[j]){
if(x.second-x.first==1) continue;
auto it=lower_bound(tren.begin(),tren.end(),tuple<int,int,int>(x.first,x.second,-1));
if(it==tren.end() || get<0>(*it)!=x.first || get<1>(*it)!=x.second) novi.push_back({x.first,x.second,j});
else novi.push_back({x.first,x.second,get<2>(*it)});
}
for(auto x:tren){
int u,d,r,l;
u=get<0>(x); d=get<1>(x); l=j; r=get<2>(x)+1;
if(ud[u+1][l]==-1) continue;
if(ud[u+1][l]>r) continue;
r=ud[u+1][l];
if(prvi){
sr.push_back({l,r,u+1,d-1,klkr++,-1});
sl.push_back({r,l,u+1,d-1,klkl++,-1});
continue;
}else if(get<5>(sr[klkr++])+get<5>(sl[klkl++])!=d-u-1) continue;
#ifdef DEBUG
cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n";
#endif
res++;
}
swap(tren,novi);
} tren.clear();
if(!prvi) break;
sort(sl.begin(),sl.end(),comp2);
sort(sr.begin(),sr.end(),comp2);
prvi=false;
int pcol=-1;
int pvr=-1;
vector<pair<int,int> > kolona;
int tc=0;
for(auto &x:sr){
auto [col,vr,u,d,koji,res]=x;
if(col!=pcol){
kolona.clear();
for(int i=0;i<maxn;i++) bit[i]=0;
for(int i=0;i<n;i++) kolona.push_back(pii(ud[i][col],i));
sort(kolona.begin(),kolona.end());
pvr=-1;
tc=0;
pcol=col;
}
if(vr!=pvr){
if(pvr!=-1){
int sta=tc-1;
while(sta>=0 && kolona[sta].first==pvr){
add(kolona[sta].second,-1);
sta--;
}
}
while(tc<int(kolona.size()) && kolona[tc].first<=vr){
if(kolona[tc].first==vr) add(kolona[tc].second,1);
tc++;
}
pvr=vr;
}
get<5>(x)=query(u,d);
}
pcol=-1;
pvr=-1;
kolona.clear();
tc=0;
for(auto &x:sl){
auto [col,vr,u,d,koji,res]=x;
if(col!=pcol){
kolona.clear();
for(int i=0;i<maxn;i++) bit[i]=0;
for(int i=0;i<n;i++) kolona.push_back(pii(ul[i][col],i));
sort(kolona.begin(),kolona.end());
pvr=-1;
tc=0;
pcol=col;
}
if(vr!=pvr){
if(pvr!=-1){
int sta=tc-1;
while(sta>=0 && kolona[sta].first==pvr){
add(kolona[sta].second,-1);
sta--;
}
}
while(tc<int(kolona.size()) && kolona[tc].first<=vr){
if(kolona[tc].first==vr) add(kolona[tc].second,1);
tc++;
}
pvr=vr;
}
get<5>(x)=query(u,d);
}
sort(sl.begin(),sl.end(),comp);
sort(sr.begin(),sr.end(),comp);
}
return res;
}
