#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<pss> hor[MAXN], ver[MAXN];
map <short int, pss> ma[MAXN];
vector<array<int,4>> v;
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";
}
}
}
set<array<short int,4>> s;
for(short int i=2; i<=n-1; i++){
for(auto [l,r] : hor[i]){
if(ma[l].find(r) == ma[l].end()){
ma[l][r] = {i, i};
} else {
pii has = ma[l][r];
if(has.se == i-1){
ma[l][r].se = i;
} else ma[l][r] = {i,i};
}
pss te = ma[l][r];
for(short int p=te.fi; p<=te.se; p++)
s.insert({l,r,p,i});
}
}
for(int i=0; i<=n+1; i++) ma[i].clear();
ll ANS = 0;
for(short int j=2; j<=m-1; j++){
for(auto [l,r] : ver[j]){
if(ma[l].find(r) == ma[l].end()){
ma[l][r] = {j, j};
} else {
pii has = ma[l][r];
if(has.se == j-1){
ma[l][r].se = j;
} else ma[l][r] = {j,j};
}
pii te = ma[l][r];
for(short int p=te.fi; p<=te.se; p++){
array<short int,4> arr = {p,j,l,r};
if(s.find(arr) != s.end()) ANS++;
}
}
}
// for(auto [a,b,c,d] : v) cout <<a<<' '<<b<<' '<<c<<' '<<d<<" ab\n";
// sort(v.begin(), v.end());
// ll ANS = 0;
// for(int i=0; i+1<v.size(); i++)
// if(v[i] == v[i+1]) ANS++;
// if(ANS > min(n,m)*n*m) assert(false);
return ANS;
}
