#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;
int n,m;
vector<vector<int> > a;
int ul[maxn][maxn],ud[maxn][maxn];
set<pii> ver[maxn];
vector<int> sl[maxn][4*maxn],sr[maxn][4*maxn]; // -1 = nema, -2 = ima suvise, else = vrednost
int tmp[maxn];
void build(vector<int>* segt,int *a,int ind=1,int l=0,int r=n-1){
if(l==r){segt[ind]={a[l]}; return;}
int mid=l+(r-l)/2;
build(segt,a,2*ind,l,mid);
build(segt,a,2*ind+1,mid+1,r);
merge(segt[2*ind].begin(),segt[2*ind].end(),segt[2*ind+1].begin(),segt[2*ind+1].end(),back_inserter(segt[ind]));
}
int query(vector<int> *segt,int tl,int tr,int t,int ind=1,int l=0,int r=n-1){
if(tl<=l && r<=tr){
return upper_bound(segt[ind].begin(),segt[ind].end(),t)-lower_bound(segt[ind].begin(),segt[ind].end(),t);
}
int mid=l+(r-l)/2;
int ret=0;
if(tl<=mid) ret+=query(segt,tl,tr,t,2*ind,l,mid);
if(tr>mid) ret+=query(segt,tl,tr,t,2*ind+1,mid+1,r);
return ret;
}
int res=0;
ll count_rectangles(vector<vector<int> > _a){
swap(a,_a); n=a.size(); m=a[0].size();
for(int i=0;i<n;i++){
stack<int> stek;
for(int j=0;j<m;j++){
while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop();
if(stek.empty()) ul[i][j]=-1;
else ul[i][j]=stek.top();
stek.push(j);
} while(!stek.empty()) stek.pop();
for(int j=m-1;j>=0;j--){
while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop();
if(stek.empty()) ud[i][j]=-1;
else ud[i][j]=stek.top();
stek.push(j);
} while(!stek.empty()) stek.pop();
}
for(int i=0;i<m;i++){
stack<int> stek;
for(int j=0;j<n;j++){
while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop();
if(!stek.empty()){ver[i].emplace(pii(stek.top(),j));}
stek.push(j);
} while(!stek.empty()) stek.pop();
for(int j=n-1;j>=0;j--){
while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop();
if(!stek.empty()){ver[i].emplace(pii(j,stek.top()));}
stek.push(j);
} while(!stek.empty()) stek.pop();
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(ud[i][j]==-1) continue;
if(ud[i][j]==j+1) ud[i][j]=-1;
if(ul[i][j]==j-1) ul[i][j]=-1;
if(a[i][j]!=a[i][ud[i][j]]) continue;
ud[i][j]=-1;
}
}
return 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) tmp[j]=ul[j][i];
//build(sl[i],tmp);
for(int j=0;j<n;j++) tmp[j]=ud[j][i];
//build(sr[i],tmp);
}
// desni cosak
map<pii,int> tren;
for(int j=1;j<m;j++){
map<pii,int> novi;
for(pii x:ver[j]){
if(x.second-x.first==1) continue;
if(tren.find(x)==tren.end()) novi[x]=j;
else novi[x]=tren[x];
}
for(auto x:tren){
int u,d,r,l;
u=x.first.first; d=x.first.second; r=j; l=x.second-1;
if(ul[u+1][r]==-1) continue;
if(ul[u+1][r]<l) continue;
l=ul[u+1][r];
int klk=0;
for(int i=u+1;i<=d-1;i++) klk+=int(ud[i][l]==r);
for(int i=u+1;i<=d-1;i++) klk+=int(ul[i][r]==l);
//if(query(sr[l],u+1,d-1,r)+query(sl[r],u+1,d-1,l)!=d-u-1) continue;
if(klk!=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--){
map<pii,int> novi;
for(pii x:ver[j]){
if(x.second-x.first==1) continue;
if(tren.find(x)==tren.end()) novi[x]=j;
else novi[x]=tren[x];
}
for(auto x:tren){
int u,d,r,l;
u=x.first.first; d=x.first.second; l=j; r=x.second+1;
if(ud[u+1][l]==-1) continue;
if(ud[u+1][l]>r) continue;
r=ud[u+1][l];
int klk=0;
for(int i=u+1;i<=d-1;i++) klk+=int(ud[i][l]==r);
for(int i=u+1;i<=d-1;i++) klk+=int(ul[i][r]==l);
//if(query(sr[l],u+1,d-1,r)+query(sl[r],u+1,d-1,l)!=d-u-1) continue;
if(klk!=d-u-1) continue;
#ifdef DEBUG
cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n";
#endif
res++;
}
swap(tren,novi);
} tren.clear();
return res;
}
