#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
int tree[1<<13][1<<13];
bool b[2500][2500];
set<int>sth[2500],stw[2500];
vector<pair<int,pair<int,int>>>p;
int H,W,res;
int calc(int xl,int xr,int yl,int yr){
int a=0;
xl+=(1<<12);
xr+=(1<<12);
yl+=(1<<12);
yr+=(1<<12);
int YL=yl,YR=yr;
while(xl<xr){
if(xl&1){
yl=YL;
yr=YR;
while(yl<yr){
if(yl&1){
a+=tree[xl][yl];
}
if(~yr&1){
a+=tree[xl][yr];
}
yl=(yl+1)/2;
yr=(yr-1)/2;
}
if(yl==yr){
a+=tree[xl][yl];
}
}
if(~xr&1){
yl=YL;
yr=YR;
while(yl<yr){
if(yl&1){
a+=tree[xr][yl];
}
if(~yr&1){
a+=tree[xr][yr];
}
yl=(yl+1)/2;
yr=(yr-1)/2;
}
if(yl==yr){
a+=tree[xr][yl];
}
}
xl=(xl+1)/2;
xr=(xr-1)/2;
}
if(xl==xr){
yl=YL;
yr=YR;
while(yl<yr){
if(yl&1){
a+=tree[xl][yl];
}
if(~yr&1){
a+=tree[xl][yr];
}
yl=(yl+1)/2;
yr=(yr-1)/2;
}
if(yl==yr){
a+=tree[xl][yl];
}
}
return a;
}
void add(int x,int y){
b[x][y]=true;
x+=(1<<12);
y+=(1<<12);
int Y=y;
while(x){
y=Y;
while(y){
// cout<<"!"<<x<<' '<<y<<endl;
tree[x][y]++;
y/=2;
}
x/=2;
}
}
long long count_rectangles(vector<vector<int>>a){
H=a.size();
W=a[0].size();
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
p.push_back({a[i][j],{i,j}});
}
}
p.push_back({0xE869120,{-1,-1}});
sort(p.begin(),p.end());
for(int i=0;i<H;i++){
for(int j=-1;j<=W;j++){
sth[i].insert(j);
}
}
for(int i=0;i<W;i++){
for(int j=-1;j<=H;j++){
stw[i].insert(j);
}
}
for(int i=0;i<p.size()-1;i++){
if(i&&p[i-1].first==p[i].first)continue;
for(int j=i;p[i].first==p[j].first;j++){
add(p[j].second.first,p[j].second.second);
sth[p[j].second.first].erase(p[j].second.second);
stw[p[j].second.second].erase(p[j].second.first);
}
vector<pair<pair<int,int>,pair<int,int>>>pp;
for(int j=i;p[i].first==p[j].first;j++){
int lx,rx,ly,ry;
auto it=sth[p[j].second.first].lower_bound(p[j].second.second);
ry=*it;
it--;
ly=*it;
auto it2=stw[p[j].second.second].lower_bound(p[j].second.first);
rx=*it2;
it2--;
lx=*it2;
lx++;
rx--;
ly++;
ry--;
if(lx<=0||ly<=0||H-1<=rx||W-1<=ry)continue;
if(calc(lx-1,rx+1,ly-1,ry+1)==calc(lx,rx,ly,ry)+b[lx-1][ly-1]+b[lx-1][ry+1]+b[rx+1][ly-1]+b[rx+1][ry+1]){
pp.push_back({{lx,rx},{ly,ry}});
// cout<<"!!!"<<lx<<' '<<rx<<' '<<' '<<ly<<' '<<ry<<endl;
}
// cout<<p[i].first<<' '<<j<<" "<<lx<<' '<<rx<<" "<<ly<<' '<<ry<<' '<<calc(lx,rx,ly,ry)<<' '<<calc(lx-1,rx+1,ly-1,ry+1)<<' '<<b[lx-1][ly-1]+b[lx-1][ry+1]+b[rx+1][ly-1]+b[rx+1][ry+1]<<endl;
}
sort(pp.begin(),pp.end());
pp.erase(unique(pp.begin(),pp.end()),pp.end());
res+=pp.size();
}
return res;
}
