#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
int n, m;
int a[2505][2505];
int dr[2505][2505], st[2505][2505], sus[2505][2505], jos[2505][2505];///ultimul pe care il bate in directia aia
int lg[2505];
short int rmqdr[13][2505][2505], rmqjos[13][2505][2505];
short int rmqst[13][2505][2505], rmqsus[13][2505][2505];
int dr2[2505][2505], st2[2505][2505], sus2[2505][2505], jos2[2505][2505];
struct gg
{
int x1, y1, x2, y2;
};
int query_dr(int col, int l, int r)
{
int lgg = lg[r - l + 1];
return min(rmqdr[lgg][l][col], rmqdr[lgg][r - (1 << lgg) + 1][col]);
}
int query_st(int col, int l, int r)
{
int lgg = lg[r - l + 1];
return max(rmqst[lgg][l][col], rmqst[lgg][r - (1 << lgg) + 1][col]);
}
int query_sus(int lin, int l, int r)
{
int lgg = lg[r - l + 1];
return max(rmqsus[lgg][lin][l], rmqsus[lgg][lin][r - (1 << lgg) + 1]);
}
int query_jos(int lin, int l, int r)
{
int lgg = lg[r - l + 1];
return min(rmqjos[lgg][lin][l], rmqjos[lgg][lin][r - (1 << lgg) + 1]);
}
bool ok(gg k)
{
int x1 = k.x1, x2 = k.x2, y1 = k.y1, y2 = k.y2;
if (x1 > x2 or y1 > y2 or x1 <= 1 or x2 >= n or y1 <= 1 or y2 >= m)
return false;
int f1 = query_dr(y1 - 1, x1, x2);
int f2 = query_st(y2 + 1, x1, x2);
int f3 = query_jos(x1 - 1, y1, y2);
int f4 = query_sus(x2 + 1, y1, y2);
gg ret;
if (f1 >= y2 and f2 <= y1 and f3 >= x2 and f4 <= x1)
return true;
return false;
}
long long count_rectangles(vector<vector<int>> A)
{
n = A.size();
m = A[0].size();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = A[i - 1][j - 1];
for (int i = 1; i <= n; i++)
{
stack<int> s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and a[i][j] > a[i][s.top()])
s.pop();
if (s.empty())
st[i][j] = 1;
else
st[i][j] = s.top() + 1;
s.push(j);
}
while (!s.empty())
s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and a[i][j] > a[i][s.top()])
s.pop();
if (s.empty())
dr[i][j] = m;
else
dr[i][j] = s.top() - 1;
s.push(j);
}
while (!s.empty())
s.pop();
}
for (int i = 1; i <= m; i++)
{
stack<int> s;
for (int j = 1; j <= n; j++)
{
while (!s.empty() and a[j][i] > a[s.top()][i])
s.pop();
if (s.empty())
sus[j][i] = 1;
else
sus[j][i] = s.top() + 1;
s.push(j);
}
while (!s.empty())
s.pop();
for (int j = n; j >= 1; j--)
{
while (!s.empty() and a[j][i] > a[s.top()][i])
s.pop();
if (s.empty())
jos[j][i] = n;
else
jos[j][i] = s.top() - 1;
s.push(j);
}
while (!s.empty())
s.pop();
}
for (int i = 2; i <= 2500; i++)
lg[i] = 1 + lg[i / 2];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
rmqdr[0][i][j] = dr[i][j];
rmqst[0][i][j] = st[i][j];
rmqsus[0][i][j] = sus[i][j];
rmqjos[0][i][j] = jos[i][j];
}
}
for (int pas = 1; pas <= 12; pas++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m - (1 << pas) + 1; j++)
{
rmqjos[pas][i][j] = min(rmqjos[pas - 1][i][j], rmqjos[pas - 1][i][j + (1 << (pas - 1))]);
rmqsus[pas][i][j] = max(rmqsus[pas - 1][i][j], rmqsus[pas - 1][i][j + (1 << (pas - 1))]);
}
}
for (int j = 1; j <= m; j++)
{
for (int i = 1; i <= n - (1 << pas) + 1; i++)
{
rmqdr[pas][i][j] = min(rmqdr[pas - 1][i][j], rmqdr[pas - 1][i + (1 << (pas - 1))][j]);
rmqst[pas][i][j] = max(rmqst[pas - 1][i][j], rmqst[pas - 1][i + (1 << (pas - 1))][j]);
}
}
}
vector<gg> sol;
for (int i = 1; i <= n; i++)
{
stack<int> s;
for (int j = 1; j <= m; j++)
{
while (!s.empty() and a[i][j] >= a[i][s.top()])
s.pop();
if (s.empty())
st2[i][j] = 1;
else
st2[i][j] = s.top() + 1;
s.push(j);
}
while (!s.empty())
s.pop();
for (int j = m; j >= 1; j--)
{
while (!s.empty() and a[i][j] >= a[i][s.top()])
s.pop();
if (s.empty())
dr2[i][j] = m;
else
dr2[i][j] = s.top() - 1;
s.push(j);
}
while (!s.empty())
s.pop();
}
for (int i = 1; i <= m; i++)
{
stack<int> s;
for (int j = 1; j <= n; j++)
{
while (!s.empty() and a[j][i] >= a[s.top()][i])
s.pop();
if (s.empty())
sus2[j][i] = 1;
else
sus2[j][i] = s.top() + 1;
s.push(j);
}
while (!s.empty())
s.pop();
for (int j = n; j >= 1; j--)
{
while (!s.empty() and a[j][i] >= a[s.top()][i])
s.pop();
if (s.empty())
jos2[j][i] = n;
else
jos2[j][i] = s.top() - 1;
s.push(j);
}
while (!s.empty())
s.pop();
}
for (int i = 2; i < n; i++)
{
for (int j = 2; j < m; j++)
{
gg aux;
aux.x1 = sus2[i][j];
aux.x2 = jos2[i][j];
aux.y1 = st2[i][j];
aux.y2 = dr2[i][j];
if (ok(aux))
sol.push_back(aux);
}
}
sort(sol.begin(), sol.end(), [](gg u, gg v){
vector<int> vu = {u.x1, u.y1, u.x2, u.y2};
vector<int> vv = {v.x1, v.y1, v.x2, v.y2};
return vu < vv;
});
if (sol.empty())
return 0ll;
long long rs = 1;
for (int i = 1; i < sol.size(); i++)
if (sol[i].x1 != sol[i - 1].x1 or sol[i].y1 != sol[i - 1].y1 or sol[i].x2 != sol[i - 1].x2 or sol[i].y2 != sol[i - 1].y2)
rs++;
return rs;
}
