#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT
{
int n;
vector<int> ft;
void init(int N)
{
n = N + 5;
ft.assign(n + 5, 0);
}
void add(int pos, int val)
{
for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
}
int get(int pos, int res = 0)
{
for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
return res;
}
};
long long count_rectangles(vector<vector<int32_t>> a)
{
int n = a.size(), m = a[0].size();
int pre[n][m], nxt[n][m];
vector<int> addR[n][m], addC[n][m];
vector<int> v;
for (int i = 0; i < n; i++)
{
v.clear();
for (int j = 0; j < m; j++)
{
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (!v.empty()) pre[i][j] = v.back() + 1;
else pre[i][j] = -1;
v.push_back(j);
}
v.clear();
for (int j = m - 1; j >= 0; j--)
{
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (!v.empty()) nxt[i][j] = v.back() - 1;
else nxt[i][j] = -1;
v.push_back(j);
}
for (int j = 0; j < m; j++)
{
if (nxt[i][j] == -1 || pre[i][j] == -1) continue;
addR[i][nxt[i][j]].push_back(pre[i][j]);
}
}
for (int j = 0; j < m; j++)
{
v.clear();
for (int i = 0; i < n; i++)
{
while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
if (!v.empty()) pre[i][j] = v.back() + 1;
else pre[i][j] = -1;
v.push_back(i);
}
v.clear();
for (int i = n - 1; i >= 0; i--)
{
while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
if (!v.empty()) nxt[i][j] = v.back() - 1;
else nxt[i][j] = -1;
v.push_back(i);
}
for (int i = 0; i < n; i++)
{
if (nxt[i][j] == -1 || pre[i][j] == -1) continue;
addC[nxt[i][j]][j].push_back(pre[i][j]);
}
}
BIT ft;
ft.init(max(n, m));
long long res = 0;
map<array<int, 2>, int> mpC, nwC, mpR, nwR;
vector<array<int, 2>> v1, v2;
for (int j = 0; j < m; j++)
{
nwC.clear();
for (int i = 0; i < n; i++)
{
nwR.clear(), v1.clear(), v2.clear();
sort(addR[i][j].begin(), addR[i][j].end());
addR[i][j].resize(unique(addR[i][j].begin(), addR[i][j].end()) - addR[i][j].begin());
sort(addC[i][j].begin(), addC[i][j].end());
addC[i][j].resize(unique(addC[i][j].begin(), addC[i][j].end()) - addC[i][j].begin());
for (int &x : addR[i][j])
{
int x1 = j - x + 1, y1 = (mpR.find({x, j}) != mpR.end() ? mpR[{x, j}] : 0) + 1;
v1.push_back({x1, y1});
}
for (int &y : addC[i][j])
{
int x2 = i - y + 1, y2 = (mpC.find({y, i}) != mpC.end() ? mpC[{y, i}] : 0) + 1;
v2.push_back({x2, y2});
}
sort(v1.begin(), v1.end(), [&](const array<int, 2> &x, const array<int, 2> &y)
{
return x[1] < y[1];
});
sort(v2.begin(), v2.end(), [&](const array<int, 2> &x, const array<int, 2> &y)
{
return x[0] < y[0];
});
int y = 0;
for (int x = 0; x < v1.size(); x++)
{
while (y < v2.size() && v1[x][1] >= v2[y][0])
{
ft.add(v2[y][1], 1);
y++;
}
res = res + 1LL * ft.get(max(n, m)) - ft.get(v1[x][0] - 1);
}
for (int x = 0; x < y; x++) ft.add(v2[x][1], -1);
for (int &x : addR[i][j]) nwR[{x, j}] = mpR[{x, j}] + 1;
for (int &y : addC[i][j]) nwC[{y, i}] = mpC[{y, i}] + 1;
mpR = nwR;
}
mpC = nwC;
}
return res;
}
