#include"rect.h"
#include<algorithm>
#include<unordered_set>
#include<set>
#include<iostream>
using namespace std;
typedef long long ll;
int gap_right[2500][2500];
int gap_down[2500][2500];
short gap_down_min[2500][2500][12];
int gap_left[2500][2500];
int gap_up[2500][2500];
int arr[2500][2500];
int highest_pow2[2501];
int w,h;
void setup(){
for(int i=1;i<2501;i++){
int pow2=0;
while((1<<pow2)<=i)
pow2++;
highest_pow2[i]=pow2-1;
}
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
gap_down_min[x][y][0]=x;
}
for(int p=1;p<12;p++){
for(int x=0;x<w-(1<<(p-1));x++){
int val1=gap_down[gap_down_min[x][y][p-1]][y];
int val2=gap_down[gap_down_min[x+(1<<(p-1))][y][p-1]][y];
if(val1<val2){
gap_down_min[x][y][p]=gap_down_min[x][y][p-1];
}else{
gap_down_min[x][y][p]=gap_down_min[x+(1<<(p-1))][y][p-1];
}
}
}
}
}
int get_min_down(int y,int x1,int x2){
/*int res=2500;
for(int x=x1;x<x2;x++)
res=min(res,gap_down[x][y]);
return res;*/
if(x1==x2)
return 2500;
int pow2=highest_pow2[x2-x1];
return min(gap_down[gap_down_min[x1][y][pow2]][y],gap_down[gap_down_min[x2-(1<<pow2)][y][pow2]][y]);
}
int get_max_up(int y,int x1,int x2){
int res=-1;
for(int x=x1;x<x2;x++)
res=max(res,gap_up[x][y]);
return res;
}
int get_min_right(int x,int y1,int y2){
int res=2500;
for(int y=y1;y<y2;y++)
res=min(res,gap_right[x][y]);
return res;
}
int get_max_left(int x,int y1,int y2){
int res=-1;
for(int y=y1;y<y2;y++)
res=max(res,gap_left[x][y]);
return res;
}
void process_column(int x){
vector<pair<int,int>>vals;
for(int y=0;y<h;y++){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_up[x][y]=-1;
if(!vals.empty())
gap_up[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],y);
}
vals.clear();
for(int y=h-1;y>=0;y--){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_down[x][y]=2500;
if(!vals.empty())
gap_down[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],y);
}
}
void process_row(int y){
vector<pair<int,int>>vals;
for(int x=0;x<w;x++){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_left[x][y]=-1;
if(!vals.empty())
gap_left[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],x);
}
vals.clear();
for(int x=w;x>=0;x--){
while(!vals.empty()&&vals.back().first<arr[x][y])
vals.pop_back();
gap_right[x][y]=2500;
if(!vals.empty())
gap_right[x][y]=vals.back().second;
vals.emplace_back(arr[x][y],x);
}
}
int check1(int x1,int x2,int y){
if(x1==-1||x2==2500||x1==x2-1)
return 0;
int y1=y-1;
int y2=get_min_down(y1,x1+1,x2);
if(y2>=h)
return 0;
if(y1==y2-1)
return 0;
if(get_max_up(y2,x1+1,x2)>y1)
return 0;
if(get_min_right(x1,y1+1,y2)<x2)
return 0;
if(get_max_left(x2,y1+1,y2)>x1)
return 0;
for(int x=x1+1;x<x2;x++)
if(gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)
return 0;
for(int y=y1+1;y<y2;y++)
if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
return 0;
return 1;
}
int check2(int x1,int x2,int y){
if(x1==-1||x2==2500||x1==x2-1)
return 0;
int y2=y+1;
int y1=get_max_up(y2,x1+1,x2);
if(y1==-1)
return 0;
if(y1==y2-1)
return 0;
if(get_min_down(y1,x1+1,x2)<y2)
return 0;
if(get_min_right(x1,y1+1,y2)<x2)
return 0;
if(get_max_left(x2,y1+1,y2)>x1)
return 0;
for(int x=x1+1;x<x2;x++)
if((gap_down[x][y1]!=y2&&gap_up[x][y2]!=y1)||gap_down[x][y1]==y2)
return 0;
for(int y=y1+1;y<y2;y++)
if(gap_right[x1][y]!=x2&&gap_left[x2][y]!=x1)
return 0;
return 1;
}
int check(int x1,int x2,int y){
return check1(x1,x2,y)+check2(x1,x2,y);
}
ll count_rectangles(vector<vector<int>>a_){
h=(int)a_.size();
w=(int)a_[0].size();
for(int x=0;x<w;x++){
for(int y=0;y<h;y++){
arr[x][y]=a_[y][x];
}
}
for(int x=0;x<w;x++)
process_column(x);
for(int y=0;y<h;y++)
process_row(y);
setup();
ll res=0;
for(int x=0;x<w;x++)
for(int y=1;y<h-1;y++){
res+=check(x,gap_right[x][y],y);
if(arr[gap_left[x][y]][y]!=arr[x][y])
res+=check(gap_left[x][y],x,y);
}
return res;
}
