#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
// #define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
typedef pair<short int, short int> pss;
const int MAXN = 2550;
const int MAXA = 2e5+10;
const int SQRT = 450;
const ll INF = 2e12;
const int MOD = 998244353;
const int LOG = 30;
int sum(int a, int b){
int te = a+MOD+b;
for(; te >= MOD; ) te -= MOD;
return te;
}
void chsum(int &a, int b){ a = sum(a,b); }
int mul(int a, int b){ return a*b%MOD; }
void chmul(int &a, int b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int a[MAXN][MAXN], n, m;
short int le[MAXN], ri[MAXN], tag[MAXN];
void upd(int x){
tag[x] = 1;
int l = x, r = x;
if(tag[x-1] == 1) l = le[x-1];
if(tag[x+1] == 1) r = ri[x+1];
le[l] = le[r] = le[x] = l; ri[l] = ri[r] = ri[x] = r;
}
vector<pii> hor[MAXN], ver[MAXN];
unordered_map <int, pii> ma[MAXN];
vector<pii> v[MAXN][MAXN], v2[MAXN][MAXN];
long long count_rectangles(std::vector<std::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];
}
if(n<=2 || m<=2) return 0;
for(int i=2; i<=n-1; i++){
vector<pii> vec;
for(int j=1; j<=m; j++) vec.pb({a[i][j], j});
sort(vec.begin(), vec.end());
for(int j=0; j<=m+1; j++){
le[j] = ri[j] = j; tag[j] = 0;
}
for(auto [v, id] : vec){
upd(id);
// for(int p=1; p<=m; p++) cout << le[p] << ' '<<ri[p] << " ri\n";
int l=le[id], r=ri[id];
if(l!=1 && r!=m && a[i][l-1] > v && a[i][r+1] > v){
hor[i].pb({l, r});
// cout << i << ' '<<l<<' '<<r<<" lr\n";
}
}
}
for(int j=2; j<=m-1; j++){
vector<pii> vec;
for(int i=1; i<=n; i++) vec.pb({a[i][j], i});
sort(vec.begin(), vec.end());
for(int i=0; i<=n+1; i++){
le[i] = ri[i] = i; tag[i] = 0;
}
for(auto [v, id] : vec){
upd(id);
short int l=le[id], r=ri[id];
if(l!=1 && r!=n && a[l-1][j] > v && a[r+1][j] > v){
ver[j].pb({l, r});
// cout << j << ' '<<l<<' '<<r<<" ver\n";
}
}
}
for(int i=2; i<=n-1; i++){
for(auto [l,r] : hor[i]){
auto has = ma[l][r];
if(has.se == i-1){
ma[l][r].se = i;
} else ma[l][r] = {i,i};
// l r te.fi i
v[i][r].pb({ma[l][r].fi, l});
}
}
for(int i=0; i<=n+1; i++) ma[i].clear();
for(int j=2; j<=m-1; j++){
for(auto [l,r] : ver[j]){
auto has = ma[l][r];
if(has.se == j-1){
ma[l][r].se = j;
} else ma[l][r] = {j,j};
// te.fi j l r
v2[r][j].pb({l, ma[l][r].fi});
}
}
ll ANS = 0;
for(int i=2; i<=n-1; i++){
for(int j=2; j<=m-1; j++){
for(auto [a, b] : v[i][j]){
for(auto [x, y] : v2[i][j]){
if(a >= y && b <= x) ANS++;
}
}
}
}
return ANS;
}
