#include <bits/stdc++.h>
#include "rect.h"
#pragma GCC optimize("O3")
using namespace std;
const int N = 2500, M = 2500;
int n, m;
long long sol;
int f[N][M], dx[]={0,1,0,-1}, dy[]={1,0,-1,0};
void bf(int x, int y, int X, int Y, vector<int> r, vector<int> c){
if(X == n-1 || Y == m-1) return;
int t = 1;
for(int i = x; i <= X; i++){
if(r[i] >= f[i][y-1]) return;
if(r[i] >= f[i][Y+1]) t = 0;
}
for(int j = y; j <= Y; j++){
if(c[j] >= f[x-1][j]) return;
if(c[j] >= f[X+1][j]) t = 0;
}
sol += t;
if(y == Y){
vector<int> cr = r, cc = c;
cr[X+1] = f[X+1][y];
cc[y] = max(cc[y], f[X+1][y]);
bf(x, y, X+1, Y, cr, cc);
}
vector<int> cr = r, cc = c;
for(int i = x; i <= X; i++) cr[i] = max(cr[i], f[i][Y+1]), cc[Y+1] = max(cc[Y+1], f[i][Y+1]);
bf(x, y, X, Y+1, cr, cc);
}
void st1(){
for(int i = 1; i < n-1; i++){
for(int j = 1; j < m-1; j++){
vector<int> r(n), c(m);
r[i] = f[i][j], c[j] = f[i][j];
bf(i, j, i, j, r, c);
}
}
}
void st5(){
for(int i = 1, mx; i < m-1; i++){
mx = 0;
for(int j = i; j < m-1; j++){
mx = max(mx, f[1][j]);
if(f[1][j] >= f[1][i-1] || f[1][j] >= f[0][j] || f[1][j] >= f[2][j]) break;
if(mx < f[1][j+1]) sol++;
}
}
}
int vis[N][M];
void flood(int x, int y, int &maxx, int &maxy, int &minx, int &miny, int &c){
if(x < 0 || y < 0 || x == n || y == m || vis[x][y] || f[x][y]) return;
c++;
vis[x][y] = 1;
maxx = max(maxx, x), minx = min(minx, x);
maxy = max(maxy, y), miny = min(miny, y);
for(int k = 0, i, j; k < 4; k++){
i = x+dx[k], j = y+dy[k];
flood(i, j, maxx, maxy, minx, miny, c);
}
}
void st6(){
for(int i = 1; i < n-1; i++){
for(int j = 1; j < m-1; j++){
if(vis[i][j] || f[i][j]) continue;
int maxx = i, minx = i, maxy = j, miny = j, c = 0;
flood(i, j, maxx, maxy, minx, miny, c);
if(minx && miny && maxx < n-1 && maxy < m-1 && c == (maxx-minx+1)*(maxy-miny+1)) sol++;
}
}
}
long long count_rectangles(vector< vector<int> > a){
n = a.size(), m = a[0].size();
if(n < 3 || m < 3) return 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
f[i][j] = a[i][j];
int s6 = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(f[i][j] > 1) s6 = 0;
if(n == 3) st5();
else if(s6) st6();
else st1();
return sol;
}
