#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define pii pair<int,int>
#define F first
#define S second
const int MX = 205;
int n,m;
bitset<MX> hor[MX][MX],ver[MX][MX];
bitset<MX> gg[MX];
bool vis[MX][MX];
vector<pii> cc;
vector<vi> A;
bool reach(int x,int y){
if(x < 0 or y < 0 or x >= n or y >= m) return 0;
if(vis[x][y]) return 0;
return A[x][y] == 0;
}
void dfs(int x,int y){
// cout << x << " " << y << endl;
cc.pb({x,y});
vis[x][y] = 1;
if(reach(x+1,y)) dfs(x+1,y);
if(reach(x-1,y)) dfs(x-1,y);
if(reach(x,y+1)) dfs(x,y+1);
if(reach(x,y-1)) dfs(x,y-1);
}
ll count_rectangles(vector<vi> a) {
n = a.size();
m = a[0].size();
A = a;
if(n <= 2) return 0;
ll ans = 0;
if(n == 3){
FOR(i,1,m-1){
int mx = -1;
FOR(j,i,m-1){
if(a[1][j] >= min(a[0][j],a[2][j])) break;
mx = max(mx,a[1][j]);
ans += (mx < min(a[1][i-1],a[1][j+1]));
}
}
return ans;
}
if(n <= 200 and m <= 200){
REP(i,n){
REP(j,m){
int mx = -1;
FOR(k,j,m){
mx = max(mx,a[i][k]);
hor[j][k][i] = (j and k < m-1 and mx < min(a[i][j-1],a[i][k+1]));
}
}
}
REP(j,m){
REP(i,n){
int mx = -1;
FOR(k,i,n){
mx = max(mx,a[k][j]);
ver[i][k][j] = (i and k < n-1 and mx < min(a[i-1][j],a[k+1][j]));
}
}
}
REP(i1,n){
REP(j1,m){
FOR(i2,i1,n){
gg[i2].reset();
}
FOR(i2,i1,n){
FOR(j2,j1,m){
if(!ver[i1][i2][j2]) break;
gg[i2][j2] = 1;
}
}
FOR(j2,j1,m){
FOR(i2,i1,n){
if(!hor[j1][j2][i2]) break;
ans += gg[i2][j2];
}
}
}
}
return ans;
}
REP(i,n) REP(j,m) vis[i][j] = 0;
REP(i,n){
REP(j,m){
if(!reach(i,j)) continue;
cc.clear();
dfs(i,j);
int mnx = cc[0].F,mxx = cc[0].F,mny = cc[0].S,mxy = cc[0].S;
for(auto bruh:cc){
mnx = min(mnx,bruh.F);
mny = min(mny,bruh.S);
mxx = max(mxx,bruh.F);
mxy = max(mxy,bruh.S);
}
// cout << mnx << " " << mxx << " " << mny << " " << mxy << endl;
if(mnx == 0 or mny == 0) continue;
if(mxx == n-1 or mxy == m-1) continue;
ans += ((mxx-mnx+1)*(mxy-mny+1) == (int)cc.size());
}
}
return ans;
}
