#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())
using ll = long long;
struct rectangle{
int x1, y1, x2, y2;
friend bool operator< (const rectangle& lhs, const rectangle& rhs){
if (lhs.x1 != rhs.x1) return lhs.x1 < rhs.x1;
if (lhs.y1 != rhs.y1) return lhs.y1 < rhs.y1;
if (lhs.x2 != rhs.x2) return lhs.x2 < rhs.x2;
return lhs.y2 < rhs.y2;
}
friend bool operator== (const rectangle& lhs, const rectangle& rhs){
return lhs.x1 == rhs.x1 and lhs.y1 == rhs.y1 and lhs.x2 == rhs.x2 and lhs.y2 == rhs.y2;
}
};
const int N = 2500 + 5;
const int inf = 1e8 + 7;
int n, m;
int a[N][N];
int nxt_u[N][N];
int nxt_l[N][N];
int nxt_r[N][N];
int nxt_d[N][N];
vector <rectangle> candidates;
vector <bool> possible;
int tmp[N];
ll count_rectangles(vector <vector <int>> _a){
n = isz(_a);
m = isz(_a.front());
ForE(i, 0, n + 1){
ForE(j, 0, m + 1){
if (i == 0 or i == n + 1 or j == 0 or j == m + 1){
a[i][j] = inf;
continue;
}
a[i][j] = _a[i - 1][j - 1];
}
}
ForE(i, 1, n){
vector <int> st = {0};
ForE(j, 1, m){
while (a[i][st.back()] < a[i][j]){
st.pop_back();
}
nxt_l[i][j] = st.back();
st.emplace_back(j);
}
st = {m + 1};
FordE(j, m, 1){
while (a[i][st.back()] < a[i][j]){
st.pop_back();
}
nxt_r[i][j] = st.back();
st.emplace_back(j);
}
}
ForE(j, 1, m){
vector <int> st = {0};
ForE(i, 1, n){
while (a[st.back()][j] < a[i][j]){
st.pop_back();
}
nxt_u[i][j] = st.back();
st.emplace_back(i);
}
st = {n + 1};
FordE(i, n, 1){
while (a[st.back()][j] < a[i][j]){
st.pop_back();
}
nxt_d[i][j] = st.back();
st.emplace_back(i);
}
}
ForE(x, 2, n - 1){
ForE(y, 2, m - 1){
{ // ul corner is SS
int tx = nxt_d[x - 1][y] - 1, ty = nxt_r[x][y - 1] - 1;
if (x <= tx and tx <= n - 1 and y <= ty and ty <= m - 1){
candidates.emplace_back(rectangle{x, y, tx, ty});
}
}
{ // ur corner is SS
int tx = nxt_d[x - 1][y] - 1, ty = nxt_l[x][y + 1] + 1;
if (x <= tx and tx <= n - 1 and 2 <= ty and ty <= y){
candidates.emplace_back(rectangle{x, ty, tx, y});
}
}
{ // dl corner is SS
int tx = nxt_u[x + 1][y] + 1, ty = nxt_r[x][y - 1] - 1;
if (2 <= tx and tx <= x and y <= ty and ty <= m - 1){
candidates.emplace_back(rectangle{tx, y, x, ty});
}
}
{ // dr corner is SS
int tx = nxt_u[x + 1][y] + 1, ty = nxt_l[x][y + 1] + 1;
if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
candidates.emplace_back(rectangle{tx, ty, x, y});
}
}
{ // dr corner is SL
int tx = nxt_u[x + 1][y] + 1, ty = nxt_l[tx][y + 1] + 1;
if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
candidates.emplace_back(rectangle{tx, ty, x, y});
}
}
{ // dr corner is LS
int ty = nxt_l[x][y + 1] + 1, tx = nxt_u[x + 1][ty] + 1;
if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
candidates.emplace_back(rectangle{tx, ty, x, y});
}
}
}
}
sort(candidates.begin(), candidates.end());
candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
possible.assign(isz(candidates), true);
For(i, 0, isz(candidates)){
auto &[x1, y1, x2, y2] = candidates[i];
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
ForE(y, y1, y2){
if (nxt_d[x1 - 1][y] != x2 + 1 and nxt_u[x2 + 1][y] != x1 - 1){
possible[i] = false;
break;
}
}
if (not possible[i]){
continue;
}
ForE(x, x1, x2){
if (nxt_r[x][y1 - 1] != y2 + 1 and nxt_l[x][y2 + 1] != y1 - 1){
possible[i] = false;
break;
}
}
}
return accumulate(possible.begin(), possible.end(), 0);
}
