#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2505;
int stk[N], to_l[N], to_r[N], w[N], last_v[N][N], last_h[N][N], c_v[N][N], c_h[N][N];
vector<int> lt[N][N], up[N][N];
void handle(int len) {
fill(to_l, to_l + len, -1);
fill(to_r, to_r + len, -1);
int z = 0;
for (int i = 0; i < len; i++) {
while (z > 0 && w[stk[z - 1]] <= w[i]) {
to_r[stk[--z]] = i;
}
stk[z++] = i;
}
z = 0;
for (int i = len - 1; i >= 0; i--) {
while (z > 0 && w[stk[z - 1]] <= w[i]) {
to_l[stk[--z]] = i;
}
stk[z++] = i;
}
}
ll count_rectangles(vector<vector<int>> a) {
// w[0] = 1;
// w[1] = 0;
// w[2] = 1;
// handle(3);
// for (int i = 0; i < 3; i++) {
// cout << to_l[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < 3; i++) {
// cout << to_r[i] << " ";
// }
// cout << "\n";
// return 0;
int n = a.size(),
m = a[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
w[j] = a[i][j];
handle(m);
for (int j = 0; j < m; j++) {
if (to_l[j] != -1 && to_l[j] + 1 < j) {
lt[i][j - 1].push_back(to_l[j] + 1);
}
if (to_r[j] != -1 && to_l[to_r[j]] != j && j + 1 < to_r[j]) {
lt[i][to_r[j] - 1].push_back(j + 1);
}
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
w[i] = a[i][j];
}
handle(n);
for (int i = 0; i < n; i++) {
if (to_l[i] != -1 && to_l[i] + 1 < i) {
up[i - 1][j].push_back(to_l[i] + 1);
}
if (to_r[i] != -1 && to_l[to_r[i]] != i && i + 1 < to_r[i]) {
up[to_r[i] - 1][j].push_back(i + 1);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
last_v[i][j] = -1;
last_h[i][j] = -1;
}
}
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int x : lt[i][j]) {
if (last_v[j][x] != i - 1)
c_v[j][x] = 0;
last_v[j][x] = i;
c_v[j][x]++;
}
for (int x : up[i][j]) {
if (last_h[i][x] != j - 1)
c_h[i][x] = 0;
last_h[i][x] = j;
c_h[i][x]++;
for (int y : lt[i][j]) {
if (i - c_v[j][y] + 1 <= x && j - c_h[i][x] + 1 <= y)
ans++;
}
}
}
}
return ans;
}
