#include "rect.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
const int N = 2505;
int n, m, dp[N][N];
vector<vector<int>> a;
inline bool check(int r1, int c1, int r2, int c2){
for(int i=r1;i<=r2;i++){
for(int j=c1;j<=c2;j++){
int t = min(min(a[i][c1-1], a[i][c2+1]), min(a[r1-1][j], a[r2+1][j]));
if(a[i][j] >= t)return false;
}
}return true;
}
ll count_rectangles(vector<vector<int>> a){
::a = a;
n = a.size();
m = a[0].size();
ll ans = 0;
if(n*m <= 1){
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
for(int I=i;I<n-1;I++){
for(int J=j;J<m-1;J++){
ans += check(i,j,I,J);
}
}
}
}return ans;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i == 0)dp[i][j]=a[i][j]^1;
else if(a[i][j] == 0)dp[i][j]=dp[i-1][j]+1;
else dp[i][j] = 0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int c=1;
bool ok = (i+1<n&&dp[i+1][j]==0);
while(j+1 < m && dp[i][j+1] == dp[i][j]){j++,c++;if(i+1<n&&dp[i+1][j]!=0)ok=false;}
int lst = j-c;
if(lst < 0)continue;
for(int k=0;k<dp[i][j];k++)ok &= (dp[i-k][lst]==0);
lst = j+1;
if(lst >= m)continue;
for(int k=0;k<dp[i][j];k++)ok &= (dp[i-k][lst]==0);
if(dp[i][j] != 0 && j - c+1 != 0 && j != m-1 && i != n-1 && i != 0 && dp[i][j+1] == 0 && dp[i][j-c] == 0&&ok)ans++;
}
}
return ans;
}
