#include "rect.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,a[2505][2505];
int L[2505][2505],R[2505][2505],U[2505][2505],D[2505][2505];
stack <pi> s;
vec N[2505][2505],M[2505][2505];
vector <pair<pi,pi>> V;
void make_LRUD() {
for(int i = 1;i <= n;i++) {
s.push({INF,-1});
for(int j = 1;j <= m;j++) {
while(s.top().x <= a[i][j]) s.pop();
L[i][j] = s.top().y;
s.push({a[i][j],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= n;i++) {
s.push({INF,-1});
for(int j = m;j >= 1;j--) {
while(s.top().x <= a[i][j]) s.pop();
R[i][j] = s.top().y;
s.push({a[i][j],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= m;i++) {
s.push({INF,-1});
for(int j = 1;j <= n;j++) {
while(s.top().x <= a[j][i]) s.pop();
U[j][i] = s.top().y;
s.push({a[j][i],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= m;i++) {
s.push({INF,-1});
for(int j = n;j >= 1;j--) {
while(s.top().x <= a[j][i]) s.pop();
D[j][i] = s.top().y;
s.push({a[j][i],j});
}
while(!s.empty()) s.pop();
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
if(sx != -1&&ex != -1) N[sx][ex].pb(j);
if(sy != -1&&ey != -1) M[sy][ey].pb(i);
}
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) sort(all(N[i][j])), N[i][j].erase(unique(all(N[i][j])),N[i][j].end());
}
for(int i = 1;i <= m;i++) {
for(int j = 1;j <= m;j++) sort(all(M[i][j])), M[i][j].erase(unique(all(M[i][j])),M[i][j].end());
}
}
ll count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) a[i+1][j+1] = A[i][j];
}
make_LRUD();
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
int sx = U[i][j], sy = L[i][j], ex = D[i][j], ey = R[i][j];
if(sx == -1||sy == -1||ex == -1||ey == -1) continue;
int L = upper_bound(all(N[sx][ex]),sy)-N[sx][ex].begin();
int R = lower_bound(all(N[sx][ex]),ey)-N[sx][ex].begin()-1;
if(L == N[sx][ex].size()||R == -1||R-L != ey-sy-2) continue;
L = upper_bound(all(M[sy][ey]),sx)-M[sy][ey].begin();
R = lower_bound(all(M[sy][ey]),ex)-M[sy][ey].begin()-1;
if(L == M[sy][ey].size()||R == -1||R-L != ex-sx-2) continue;
V.pb({{sx,sy},{ex,ey}});
}
}
sort(all(V)), V.erase(unique(all(V)),V.end());
return V.size();
}
