#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
const int N = 2500 + 7;
int v[N];
int stk[N];
int top;
int l[N];
int r[N];
vector<pair<int, int>> potential(vector<int> b)
{
int n = (int) b.size();
for (int i = 1; i <= n;i ++)
{
v[i] = b[i - 1];
}
top = 0;
stk[0] = 0;
for (int i = 1; i <= n; i++)
{
while (top && v[stk[top]] < v[i])
{
top--;
}
l[i] = stk[top];
stk[++top] = i;
}
top = 0;
stk[0] = n + 1;
for (int i = n; i >= 1; i--)
{
while (top && v[stk[top]] < v[i])
{
top--;
}
r[i] = stk[top];
stk[++top] = i;
}
vector<pair<int, int>> sol;
for (int i = 1; i <= n; i++)
{
int j = l[i];
if (1 <= j && i - j >= 2)
{
sol.push_back({j, i});
}
j = r[i];
if (j <= n && j - i >= 2)
{
sol.push_back({i, j});
}
}
for (auto &it : sol)
{
it.first--;
it.second--;
it.first++;
it.second--;
}
if (sol.empty())
{
return sol;
}
sort(sol.begin(), sol.end());
vector<pair<int, int>> sol2;
sol2.push_back(sol[0]);
for (int i = 1; i < (int) sol.size(); i++)
{
if (sol[i] != sol[i - 1])
{
sol2.push_back(sol[i]);
}
}
return sol2;
}
vector<vector<pair<int, int>>> pot_row;
vector<vector<pair<int, int>>> pot_col;
bool has_row(int r, pair<int, int> it)
{
int lo = 0, hi = (int) pot_row[r].size() - 1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (pot_row[r][mid] == it)
{
return 1;
}
if (pot_row[r][mid] < it)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return 0;
}
bool has_col(int c, pair<int, int> it)
{
int lo = 0, hi = (int) pot_col[c].size() - 1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (pot_col[c][mid] == it)
{
return 1;
}
if (pot_col[c][mid] < it)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return 0;
}
bool check(int r1, int c1, int r2, int c2)
{
for (int r = r1; r <= r2; r++)
{
if (has_row(r, {c1, c2}) == 0)
{
return 0;
}
}
for (int c = c1; c <= c2; c++)
{
if (has_col(c, {r1, r2}) == 0)
{
return 0;
}
}
return 1;
}
long long count_rectangles(vector<vector<int>> a)
{
int n = (int) a.size();
int m = (int) a[0].size();
pot_row.resize(n);
pot_col.resize(m);
vector<vector<vector<int>>> rows(n);
vector<vector<vector<int>>> cols(n);
for (int i = 0; i < n; i++)
{
rows[i].resize(m);
cols[i].resize(m);
}
for (int i = 0; i < n; i++)
{
pot_row[i] = potential(a[i]);
for (auto &it : pot_row[i])
{
cols[i][it.second].push_back(it.first);
}
}
for (int j = 0; j < m; j++)
{
vector<int> b;
for (int i = 0; i < n; i++)
{
b.push_back(a[i][j]);
}
pot_col[j] = potential(b);
for (auto &it : pot_col[j])
{
rows[it.second][j].push_back(it.first);
}
}
ll sol = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (auto &r : rows[i][j])
{
for (auto &c : cols[i][j])
{
if (check(r, c, i, j))
{
sol++;
}
}
}
}
}
return sol;
}
