#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2500 + 12;
int n, m, a[N][N], u[N][N], d[N][N], l[N][N], r[N][N], s[N][N];
void prec() {
	for(int i = 1; i <= n; i++) {
		vector<int> st;
		for(int j = 1; j <= m; j++) {
			while(!st.empty() && a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}
			l[i][j] = (st.empty() ? 0 : st.back());
			st.push_back(j);
		}
		st.clear();
		for(int j = m; j >= 1; j--) {
			while(!st.empty() && a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}
			r[i][j] = (st.empty() ? m + 1 : st.back());
			st.push_back(j);
		}
	}

	for(int j = 1; j <= m; j++) {
		vector<int> st;
		for(int i = 1; i <= n; i++) {
			while(!st.empty() && a[st.back()][j] <= a[i][j]) {
				st.pop_back();
			}
			u[i][j] = (st.empty() ? 0 : st.back());
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; i--) {
			while(!st.empty() && a[st.back()][j] <= a[i][j]) {
				st.pop_back();
			}
			d[i][j] = (st.empty() ? n + 1 : st.back());
			st.push_back(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
}
int get(int x, int y, int x1, int y1) {
	return (s[x1][y1] - s[x1][y - 1] - s[x - 1][y1] + s[x - 1][y - 1]);
}
bool check(int x, int y, int x1, int y1) {
	return (get(x, y, x1, y1) == 0);
}
bool check1(int x, int y, int x1, int y1) {
	int s = get(x, y, x1, y1);
	return (s == (x1 - x + 1) * (y1 - y + 1));
}
ll count_rectangles(vector<vector<int> > _A) {
	n = (int)_A.size();
	m = (int)_A[0].size();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = _A[i - 1][j - 1];
		}
	}
	prec();
	ll res = 0;
	for(int i = 2; i < n; i++) {
		for(int j = 2; j < m; j++) {
			if(!a[i][j]) {
				int y = l[i][j] + 1, x = u[i][j] + 1;
				if(x <= 1|| y <= 1) continue;
				// cout << x << ' ' << y << ' ' << i << ' ' << j << '\n';
				if(check(x, y, i, j)) {
					if(!check1(i + 1, y, i + 1, j)) {
						continue;
					}
					if(!check1(x - 1, y, x - 1, j)) {
						continue;
					}
					if(!check1(x, y - 1, i, y - 1)) {
						continue;
					}
					if(!check1(x, j + 1, i, j + 1)) {
						continue;
					}
					res++;
				}
			}
		}
	}
	return res;
}