#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define ss second
const int N = 2600, K = 20;
int rmq[N][K];
int get(int l, int r){
int k = int(log2(r-l+1));
return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
if(n < 3 || m < 3){
return 0;
}
if(n == 3){
vector<bool> good(m);
for(int i = 1; i + 1 < m; ++i){
if(a[1][i] < a[0][i] && a[1][i] < a[2][i]){
good[i] = 1;
}else good[i] = 0;
}
for(int i = 1; i < m; ++i) rmq[i][0] = (good[i] ? a[1][i] : INT_MAX);
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= m; ++i){
rmq[i][j] = max(rmq[i][j - 1], rmq[i+(1<<(j-1))][j-1]);
}
}
int ans = 0;
for(int i = 1; i + 1 < m; ++i){
for(int j = i; j + 1 < m; ++j){
if(get(i, j) < min(a[1][i - 1], a[1][j + 1]) && good[i]){
++ans;
}
}
}
return ans;
}
vector<vector<int>> dp(n, vector<int>(m));
ll ans = 0;
for(int i = 1; i + 1 < n; ++i){
for(int j = 1; j + 1 < m; ++j){
if(a[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i - 1][j] + 1;
}
}
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << a[i][j];
// cout << '\n';
// }
for(int i = 1; i + 1 < n; ++i){
int r = 1;
for(int j = 1; j + 1 < m; ++j){
// cout << i << ' ' << j << '\n';
if(a[i][j] == 1) continue;
// cout << i << ' ' << j << '\n';
if(a[i][j - 1] != 1) continue;
r = j;
while(r + 1 < m && a[i][r] == 0) ++r;
--r;
if(a[i][r + 1] != 1) continue;
ll sum = 0;
vector<pair<int, ll>> v;
for(int l = i; l <= r; ++l){
int co = 1;
while(!v.empty() && v.back().first > dp[i][l]){
co += v.back().second;
sum -= v.back().first * v.back().second;
v.pop_back();
}
sum += dp[i][l] * co;
v.pb({dp[i][l], co});
ans += sum;
}
// cout << i << ' ' << j << ' ' << r << ' ' << ans << '\n';
j = r;
}
}
return ans;
}
