#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;
long long count_rectangles(std::vector<std::vector<int> > a) {
bool flag=1;
int n=a.size();
int m=a[0].size();
REP(i,0,n)REP(j,0,m)if(a[i][j]>1)flag=0;
if(flag){
ll ans=0;
queue<pi> pq;
REP(i,1,n-1)REP(j,1,m-1){
if(a[i][j]==1)continue;
int c=0,d=0;
while(j+c<m-1&&a[i][j+c]==0)c++;
while(i+d<n-1&&a[i+d][j]==0)d++;
bool g=1;
REP(x,i,i+d){
if(a[x][j-1]==0||a[x][j+c]==0)g=0;
}
REP(x,j,j+c){
if(a[j][i-1]==0||a[j][i+d]==0)g=0;
}
pq.push({i,j});int k=0;
while(!pq.empty()){
int x=pq.front().F;
int y=pq.front().S;
pq.pop();
if(a[x][y]==1)continue;
a[x][y]=1;k++;
if(x+1<n-1&&a[x+1][y]==0)pq.push({x+1,y});
if(y+1<m-1&&a[x][y+1]==0)pq.push({x,y+1});
}
if(k==c*d&&g)ans++;
}
return ans;
}
vii b(n,vi(m,0)),c(n,vi(m,0));
ll ans=0;
REP(i,1,n-1)REP(j,1,m-1){
vii top(n,vi(m,0)),left(n,vi(m,0)),d(n,vi(m,0));
REP(x,i,n-1)REP(y,j,m-1){
top[x][y]=max(top[x-1][y],a[x][y]);
left[x][y]=max(left[x][y-1],a[x][y]);
}
REP(y,j,m-1)d[i-1][y]=1;
REP(x,i,n-1)REP(y,j,m-1)if(left[x][y]<a[x][j-1]&&left[x][y]<a[x][y+1]&&d[x-1][y])d[x][y]=1;
REP(x,i,n-1){
REP(y,j,m-1){
if(top[x][y]>=a[i-1][y]||top[x][y]>=a[x+1][y])break;
if(d[x][y]){
ans++;//cerr<<i<<" "<<j<<" "<<x<<" "<<y<<"\n";
}
}
}
// if(i==n-2&&j==m-2){cout<<"\n";
// REP(x,i,n-1){
// REP(y,j,m-1)cout<<d[x][y]<<" ";
// cout<<"\n";
// }
// }
}
return ans;
}
