#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 3e3 + 10;
const int lg = 20;
int n, m, spt[lg][maxn], a[maxn][maxn], l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn], ans[maxn][maxn];
int L[maxn][maxn], R[maxn][maxn], U[maxn][maxn], D[maxn][maxn];
vector<pii> Q[maxn][4];
struct rect{
int a, b, c, d;
};
int getmin(int l, int r){
r++;
int x = 31 - __builtin_clz(r-l);
return min(spt[x][l], spt[x][r-(1<<x)]);
}
int getmax(int l, int r){
r++;
int x = 31 - __builtin_clz(r-l);
return max(spt[x][l], spt[x][r-(1<<x)]);
}
ll count_rectangles(vector<vector<int>> A) {
n = A.size();
m = A[0].size();
//debug(n, m);
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
a[i][j] = A[i][j];
// debug(i, j, a[i][j]);
}
}
// debug(1);
for (int i = 0; i < n; i++){
vector<int> v;
for (int j = 0; j < m; j++){
l[i][j] = -1;
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (!v.empty()) l[i][j] = v.back();
v.push_back(j);
}
v.clear();
for (int j = m-1; ~j; j--){
r[i][j] = m;
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (!v.empty()){
r[i][j] = v.back();
// debug(i, j, v.back(), a[i][j], a[i][v.back()]);
}
v.push_back(j);
}
}
// debug(2);
for (int j = 0; j < m; j++){
vector<int> v;
for (int i = 0; i < n; i++){
u[i][j] = -1;
while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
if (!v.empty()) u[i][j] = v.back();
v.push_back(i);
}
v.clear();
for (int i = n-1; ~i; i--){
d[i][j] = n;
while (!v.empty() && a[v.back()][j] <= a[i][j]){
//debug(i, j, v.back(), a[v.back()][j], a[i][j]);
v.pop_back();
}
if (!v.empty()) d[i][j] = v.back();
v.push_back(i);
}
}
// debug(3);
for (int x = 0; x < n; x++){
for (int y = 0; y < m; y++){
// debug(x, y, l[x][y], r[x][y], u[x][y], d[x][y]);
if (l[x][y] == -1 || r[x][y] == m || d[x][y] == n || u[x][y] == -1) continue;
// debug(1);
Q[l[x][y]][0].push_back({x, y});
Q[r[x][y]][1].push_back({x, y});
Q[u[x][y]][2].push_back({x, y});
Q[d[x][y]][3].push_back({x, y});
}
}
for (int i = 0; i < n; i++){
vector<int> v;
for (int j = 0; j < m; j++){
L[i][j] = -1;
while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back();
if (!v.empty()) L[i][j] = v.back();
v.push_back(j);
}
v.clear();
for (int j = m-1; ~j; j--){
R[i][j] = m;
while (!v.empty() && a[i][v.back()] < a[i][j]) v.pop_back();
if (!v.empty()){
R[i][j] = v.back();
// debug(i, j, v.back(), a[i][j], a[i][v.back()]);
}
v.push_back(j);
}
}
// debug(2);
for (int j = 0; j < m; j++){
vector<int> v;
for (int i = 0; i < n; i++){
U[i][j] = -1;
while (!v.empty() && a[v.back()][j] < a[i][j]) v.pop_back();
if (!v.empty()) U[i][j] = v.back();
v.push_back(i);
}
v.clear();
for (int i = n-1; ~i; i--){
D[i][j] = n;
while (!v.empty() && a[v.back()][j] < a[i][j]){
//debug(i, j, v.back(), a[v.back()][j], a[i][j]);
v.pop_back();
}
if (!v.empty()) D[i][j] = v.back();
v.push_back(i);
}
}
// debug(4);
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
spt[0][j] = U[i][j];
}
for (int j = 1; j < lg; j++){
for (int k = 0; k + (1 << j) <= m; k++){
spt[j][k] = max(spt[j-1][k], spt[j-1][k+(1<<(j-1))]);
}
}
for (auto [x, y]: Q[i][3]){
if (getmax(l[x][y]+1, r[x][y]-1) <= u[x][y]) ans[x][y]++;
}
for (int j = 0; j < m; j++){
spt[0][j] = D[i][j];
}
for (int j = 1; j < lg; j++){
for (int k = 0; k + (1 << j) <= m; k++){
spt[j][k] = min(spt[j-1][k], spt[j-1][k+(1<<(j-1))]);
}
}
for (auto [x, y]: Q[i][2]){
if (getmin(l[x][y]+1, r[x][y]-1) >= d[x][y]) ans[x][y]++;
}
}
// debug(5);
for (int j = 0; j < m; j++){
// debug(j);
for (int i = 0; i < n; i++){
spt[0][i] = L[i][j];
}
for (int i = 1; i < lg; i++){
for (int k = 0; k + (1 << i) <= n; k++){
spt[i][k] = max(spt[i-1][k], spt[i-1][k+(1<<(i-1))]);
}
}
// debug(1);
for (auto [x, y]: Q[j][1]){
if (getmax(u[x][y]+1, d[x][y]-1) <= l[x][y]) ans[x][y]++;
}
// debug(2);
for (int i = 0; i < n; i++){
spt[0][i] = R[i][j];
}
for (int i = 1; i < lg; i++){
for (int k = 0; k + (1 << i) <= n; k++){
spt[i][k] = min(spt[i-1][k], spt[i-1][k+(1<<(i-1))]);
}
}
// debug(3);
for (auto [x, y]: Q[j][0]){
if (getmin(u[x][y]+1, d[x][y]-1) >= r[x][y]) ans[x][y]++;
}
// debug(4);
}
vector<pair<pii,pii>> res;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (ans[i][j] == 4) res.push_back({{l[i][j]+1, r[i][j]-1}, {u[i][j]+1, d[i][j]-1}});
}
}
sort(all(res));
res.resize(distance(res.begin(), unique(all(res))));
/*for (auto [a, b]: res){
debug(a.F, a.S, b.F, b.S);
}*/
return res.size();
}
