#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll ans = 0;
struct obdl
{
int x1, y1, x2, y2, t;
};
vector<obdl> make(vector<vector<int> > a)
{
int n = a.size(), m = a[0].size();
vector<set<pair<int, int> > > end(n);
for (int i = 0; i < n; i++)
{
vector<int> ri(m, m), li(m, -1);
vector<int> st;
for (int j = 0; j < m; j++) // najdeme najblizsi vacsi
{
while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
if (!st.empty() && st.back() + 1 < j) li[j] = st.back();
st.push_back(j);
}
st.clear();
for (int j = m - 1; j >= 0; j--) // najdeme najblizsi vacsi
{
while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
if (!st.empty() && st.back() - 1 > j) ri[j] = st.back();
st.push_back(j);
}
for (int j = 0; j < m; j++)
{
if (ri[j] != m && li[ri[j]] <= j) end[i].insert({ j + 1, ri[j] - 1 });
if (li[j] != -1 && ri[li[j]] >= j) end[i].insert({ li[j] + 1, j - 1 });
}
}
vector<obdl>o;
for (int i = 0; i < n; i++) for (pair<int, int> p : end[i])
{
int j = i + 1;
while (j < n && end[j].count(p)) end[j++].erase(p);
o.push_back({ i, p.first, j - 1, p.second });
}
return o;
}
const int maxn = 2505;
int st[maxn];
void upd(int i, int x)
{
for (; i < maxn; i = (i | (i + 1))) st[i] += x;
}
int query(int r)
{
int ans = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) ans += st[r];
return ans;
}
struct udaj { int x, y, t; };
ll count_rectangles(vector<vector<int> > a)
{
int n = a.size(), m = a[0].size();
vector<vector<vector<udaj> > > v(n, vector<vector<udaj> >(m));
vector<vector<vector<obdl> > > o(n, vector<vector<obdl> >(m));
vector<obdl> o1 = make(a);
vector<vector<int> > b(m, vector<int>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
vector<obdl> o2 = make(b);
for (obdl& i : o2) i.t = 2, swap(i.x1, i.y1), swap(i.x2, i.y2), o[i.x2][i.y2].push_back(i);
for (obdl i : o1) i.t = 1, o[i.x2][i.y2].push_back(i);
for (int x = 0; x < n; x++) for (int y = m - 1; y >= 0; y--) for (obdl i : o[x][y])
{
if (i.t == 1) for (int x1 = i.x1; x1 <= i.x2; x1++) v[x1][i.y1].push_back({ x, y, 1 });
if (i.t == 2) for (int y1 = i.y1; y1 <= i.y2; y1++) v[i.x1][y1].push_back({ x, y, 2 });
}
ll ans = 0;
for (int x = 1; x + 1 < n; x++) for (int y = 1; y + 1 < m; y++)
{
ll sum = 0, all = 0;
for (udaj u : v[x][y])
{
if (u.t == 2) upd(u.y, 1), all++;
else sum += all - query(u.y - 1);
}
for (udaj u : v[x][y]) if (u.t == 2) upd(u.y, -1);
ans += sum;
//cout << sum << " \n"[y == m - 2];
}
return ans;
}
