#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2505;
int pt,color[mxn][mxn],n,m,rw[mxn],cl[mxn],a,b;
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
bool check(int r1,int r2,int c1,int c2,vector<vector<int>>&arr){
for(int i=r1;i<=r2;i++){
for(int j=c1;j<=c2;j++){
if(arr[i][j]<arr[i][c1-1]&&arr[i][j]<arr[i][c2+1]&&arr[i][j]<arr[r1-1][j]&&arr[i][j]<arr[r2+1][j]){
}
else{
return false;
}
}
}
return true;
}
int funk(vector<vector<int>>&arr,int x,int y){
int n=(int)arr.size(), m=(int)arr[0].size();
if(arr[x-1][y]<=arr[x][y]||arr[x][y-1]<=arr[x][y]){
return 0;
}
int ans=0;
for(int i=x;i<n-1;i++){
for(int j=y;j<m-1;j++){
if(check(x,i,y,j,arr)){
ans++;
}
}
}
return ans;
}
void dfs(int i,int j,vector<vector<int>>&arr){
color[i][j]=1;
if(i==0||i==n-1||j==0||j==m-1){
pt=0;
}
rw[i]++,cl[j]++;
a=max(a,rw[i]),b=max(b,cl[j]);
for(int ind=0;ind<4;ind++){
i+=x[ind],j+=y[ind];
if(i>=0&&i<n&&j>=0&&j<m&&!color[i][j]&&!arr[i][j]){
dfs(i,j,arr);
}
i-=x[ind],j-=y[ind];
}
}
int task(vector<vector<int>>&arr){
n=arr.size(), m=arr[0].size();
int ans=0;
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
if(!color[i][j]&&arr[i][j]==0){
pt=1;
memset(rw,0,sizeof(rw));
memset(cl,0,sizeof(cl));
a=0,b=0;
dfs(i,j,arr);
if(pt){
for(int i=0;i<n;i++){
if(rw[i]>0&&rw[i]!=a){
pt=0;
break;
}
}
}
if(pt){
for(int i=0;i<m;i++){
if(cl[i]>0&&cl[i]!=b){
pt=0;
break;
}
}
}
ans+=pt;
}
}
}
return ans;
}
long long count_rectangles(vector<vector<int>>arr) {
int n=arr.size(), m=arr[0].size();
int ans=0;
bool q=true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]>1){
q=false;
break;
}
}
}
if(q){
return task(arr);
}
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
ans+=funk(arr,i,j);
}
}
return ans;
}
