#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
const int MX = 2505;
int cl[MX][MX]; // smallest row>i on same column containing one
int nxt[MX][MX]; // furthest col on same row tel que same close
int cum[MX][MX]; // normal cum on columns
int gimme(int col,int a,int b){
return cum[b][col] - (a?cum[a-1][col]:0);
}
ll count_rectangles(vector<vector<int> > a) {
ll ans=0;
int n=sz(a),m=sz(a[0]);
if(n<=3){
if(n<=2)return 0;
for (int i = 1; i < m-1; ++i)
{
if(a[1][i]>=a[1][i-1])continue;
for (int j = i; j < m-1; ++j){
if(a[1][j]>=a[0][j] || a[1][j]>=a[2][j])break;
ans+=((a[1][j]<a[1][j+1]) && (a[1][j]<a[1][i-1]) && (a[1][i]<a[1][j+1]));
}
}
return ans;
}
bool f=1;
for (int j = 0; j < m; ++j)
{
int last=-1;
for (int i = n-1; i >= 0; i--){
if(a[i][j]>1)f=0;
if(a[i][j]){
cl[i][j]=last,last=i;
if((i+1) == cl[i][j])cl[i][j]=-1;
}
else cl[i][j]=-1;
}
}
if(!f){
for (int r1 = 1; r1 <= n-2; ++r1)
for (int r2 = r1; r2 <= n-2; ++r2)
for (int c1 = 1; c1 <= m-2; ++c1)
for (int c2 = c1; c2 <= m-2; ++c2)
{
bool ok=1;
for (int i = r1; i <= r2; ++i){
for (int j = c1; j <= c2; ++j)
if(a[i][j]>=a[i][c1-1] || a[i][j]>=a[i][c2+1] || a[i][j]>=a[r1-1][j] || a[i][j]>=a[r2+1][j]){ok=0;break;}
if(!ok)break;
}
ans+=ok;
}
return ans;
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; )
{
if(cl[i][j]==-1){
nxt[i][j]=-1,j++;
continue;
}
int z=j;
while(z<m && cl[i][z]==cl[i][j])
z++;
for (int A = j; A < z; ++A)
nxt[i][A]=z;
j=z;
}
for (int j = 0; j < m; ++j){
cum[i][j]=(!a[i][j]);
if(i)cum[i][j]+=cum[i-1][j];
}
}
for (int i = 0; i < n-2; ++i)
for (int j = 1; j < m-1; ++j)
if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && nxt[i][j]!=m && !gimme(nxt[i][j],i+1,cl[i][j]-1))
ans++;
return ans;
}
