#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2600;
int n, m, w[N][N], T[N];
vector<int>Right[N][N], Down[N][N];
int st[N], RR[N], LL[N];
void PreCalc(int n) {
int top = 0;
for (int i = 1; i <= n; i ++)
RR[i] = LL[i] = 0;
for (int i = 1; i <= n; i ++) {
while (top && T[st[top]] <= T[i]) {
RR[st[top]] = i;
top --;
}
st[++ top] = i;
}
top = 0;
for (int i = n; i >= 1; i --) {
while (top && T[st[top]] <= T[i]) {
LL[st[top]] = i;
top--;
}
st[++top] = i;
}
}
int last[N][N], CC[N][N];
int lastH[N], CH[N];
struct point {
int x, y, ck;
bool operator < (const point &p) const {
return x < p.x;
}
} U[10100];
int BIT[N];
void Add(int a, int b) {
while (a <= m) {
BIT[a] += b;
a += a & -a;
}
}
int Sum(int a) {
int r = 0;
while (a) {
r += BIT[a];
a -= a & -a;
}
return r;
}
long long count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
w[i + 1][j + 1] = a[i][j];
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++)
T[j] = w[i][j];
PreCalc(m);
for (int j = 1; j <= m; j ++) {
if (RR[j] && RR[j] > j + 1)
Right[i][j + 1].push_back(RR[j] - 1);
if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)
Right[i][LL[j] + 1].push_back(j - 1);
}
}
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++)
T[j] = w[j][i];
PreCalc(n);
for (int j = 1; j <= n; j ++) {
if (RR[j] && RR[j] > j + 1)
Down[j + 1][i].push_back(RR[j] - 1);
if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)
Down[LL[j] + 1][i].push_back(j - 1);
}
}
long long res = 0;
for (int i = n; i >= 1; i --) {
for (int j = 1; j <= n; j ++)
lastH[j] = CH[j] = 0;
for (int j = m; j >= 1; j--) {
for (auto &t : Right[i][j]) {
if (last[j][t] != i + 1)
CC[j][t] = 0;
CC[j][t] ++;
last[j][t] = i;
}
for (auto &t : Down[i][j]) {
if (lastH[t] != j + 1)
CH[t] = 0;
CH[t] ++;
lastH[t] = j;
}
int cnt = 0;
for (auto &t : Right[i][j]) {
U[cnt ++] = {i, t, 1};
U[cnt ++] = {i + CC[j][t], t, -1};
}
sort(U, U + cnt);
sort(Down[i][j].begin(), Down[i][j].end());
int pv = 0;
for (auto &t : Down[i][j]) {
while (pv < cnt && U[pv].x <= t) {
Add(U[pv].y, U[pv].ck);
pv ++;
}
res += Sum(j + CH[t] - 1);
}
while (pv < cnt) {
Add(U[pv].y, U[pv].ck);
pv ++;
}
}
}
return res;
}
