#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using L = long long;
template <typename T, int64_t N>
struct FenwickTree
{
T t[N];
void update(int64_t i, T x)
{
++i;
while (i <= N)
t[i - 1] += x, i += i & -i;
}
T prefix_sum(int64_t i)
{
T x = 0;
++i;
while (i)
x += t[i - 1], i -= i & -i;
return x;
}
};
constexpr size_t N = 2501;
vector<uint16_t> h[N][N];
vector<pair<uint16_t, uint16_t>> h_[N][N], v_[N][N];
FenwickTree<int32_t, N> tree;
L count_rectangles(vector<vector<int>> a)
{
size_t const n = a.size(), m = a[0].size();
for (size_t i = 0; i < n; ++i)
{
stack<size_t> s;
for (size_t j = 0; j < m; ++j)
{
while (!s.empty() && a[i][s.top()] < a[i][j])
s.pop();
if (!s.empty() && j - s.top() >= 2)
h[s.top()][j].push_back(i);
if (!s.empty() && a[i][s.top()] == a[i][j])
s.pop();
s.push(j);
}
while (!s.empty())
s.pop();
for (size_t j = m - 1; j < m; --j)
{
while (!s.empty() && a[i][s.top()] < a[i][j])
s.pop();
if (!s.empty() && s.top() - j >= 2 && a[i][s.top()] != a[i][j])
h[j][s.top()].push_back(i);
if (!s.empty() && a[i][s.top()] == a[i][j])
s.pop();
s.push(j);
}
}
for (size_t i = 0; i < m; ++i)
for (size_t j = i + 2; j < m; ++j)
for (size_t k = 0; k < h[i][j].size();)
{
size_t l = k + 1;
while (l < h[i][j].size() && h[i][j][l] == h[i][j][l - 1] + 1)
++l;
for (size_t p = k; p < l; ++p)
if (h[i][j][p])
h_[h[i][j][p] - 1][i].emplace_back(j, h[i][j][l - 1] + 1);
k = l;
}
for (auto &x : h)
for (auto &y : x)
y = vector<uint16_t>();
for (size_t j = 0; j < m; ++j)
{
stack<size_t> s;
for (size_t i = 0; i < n; ++i)
{
while (!s.empty() && a[s.top()][j] < a[i][j])
s.pop();
if (!s.empty() && i - s.top() >= 2)
h[s.top()][i].push_back(j);
if (!s.empty() && a[s.top()][j] == a[i][j])
s.pop();
s.push(i);
}
while (!s.empty())
s.pop();
for (size_t i = n - 1; i < n; --i)
{
while (!s.empty() && a[s.top()][j] < a[i][j])
s.pop();
if (!s.empty() && s.top() - i >= 2 && a[s.top()][j] != a[i][j])
h[i][s.top()].push_back(j);
if (!s.empty() && a[s.top()][j] == a[i][j])
s.pop();
s.push(i);
}
}
for (size_t i = 0; i < n; ++i)
for (size_t j = i + 2; j < n; ++j)
for (size_t k = 0; k < h[i][j].size();)
{
size_t l = k + 1;
while (l < h[i][j].size() && h[i][j][l] == h[i][j][l - 1] + 1)
++l;
for (size_t p = k; p < l; ++p)
if (h[i][j][p])
v_[i][h[i][j][p] - 1].emplace_back(j, h[i][j][l - 1] + 1);
k = l;
}
for (auto &x : h)
for (auto &y : x)
y = vector<uint16_t>();
L ans = 0;
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < m; ++j)
{
sort(v_[i][j].begin(), v_[i][j].end(), [](auto const &a, auto const &b)
{ return a.second > b.second; });
sort(h_[i][j].begin(), h_[i][j].end(), [](auto const &a, auto const &b)
{ return a.first > b.first; });
auto it = v_[i][j].begin();
for (auto jt = h_[i][j].begin(); jt != h_[i][j].end(); ++jt)
{
while (it != v_[i][j].end() && it->second >= jt->first)
{
tree.update(it->first, 1);
++it;
}
L x = tree.prefix_sum(jt->second);
ans += x;
}
for (auto jt = v_[i][j].begin(); jt != it; ++jt)
tree.update(jt->first, -1);
v_[i][j] = vector<pair<uint16_t, uint16_t>>();
}
return ans;
}
