#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2, unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
const int inf=1000001000; // 1e9
const ll INF=10000000010000000; // 1e16
const int mod=1000000007;
const int N=2510;
ll ans; // :(
int n, m, k, x, y, u, v, t;
int A[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
vector<pii> vec[N];
int dwn[N][N<<1];
ll count_rectangles(vector<vector<int>> _A){
n=SZ(_A);
m=SZ(_A[0]);
for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++) for (L[i][j]=j-1; L[i][j] && A[i][L[i][j]]<A[i][j]; L[i][j]=L[i][L[i][j]]) ;
for (int j=m; j; j--) for (R[i][j]=j+1; R[i][j]<=m && A[i][R[i][j]]<A[i][j]; R[i][j]=R[i][R[i][j]]) ;
}
for (int j=1; j<=m; j++){
for (int i=1; i<=n; i++) for (U[i][j]=i-1; U[i][j] && A[U[i][j]][j]<A[i][j]; U[i][j]=U[U[i][j]][j]) ;
for (int i=n; i; i--) for (D[i][j]=i+1; D[i][j]<=n && A[D[i][j]][j]<A[i][j]; D[i][j]=D[D[i][j]][j]) ;
}
// debug("LRDU built")
for (int i=n; i; i--){
for (int j=1; j<=m; j++){
if (L[i][j] && j-L[i][j]>1) vec[i].pb({L[i][j], j});
if (R[i][j]<=m && R[i][j]-j>1) vec[i].pb({j, R[i][j]});
}
sort(all(vec[i]));
vec[i].resize(unique(all(vec[i]))-vec[i].begin());
for (int j=0; j<SZ(vec[i]); j++){
auto it=lower_bound(all(vec[i+1]), vec[i][j]);
if (it==vec[i+1].end() || *it!=vec[i][j]) dwn[i][j]=i;
else dwn[i][j]=dwn[i+1][it-vec[i+1].begin()];
}
}
for (int j=2; j<m; j++){
vector<pii> shit;
for (int i=1; i<=n; i++){
if (U[i][j]) shit.pb({U[i][j], i});
if (D[i][j]<=n) shit.pb({i, D[i][j]});
}
sort(all(shit)); // why?
shit.resize(unique(all(shit))-shit.begin());
for (pii p:shit) if (p.second-p.first>1){
int u=p.first, d=p.second;
if (2<j && (U[d][j-1]==u || D[u][j-1]==d)) continue ; // already counted
int l=j, r=l;
while (r+1<m && (D[u][r+1]==d || U[d][r+1]==u)) r++; // O(nm) amortized
vector<pii> shit2;
l--, r++; // :clown:
for (int i=l; i<=r; i++){
if (l<=L[u+1][i]) shit2.pb({L[u+1][i], i});
if (R[u+1][i]<=r) shit2.pb({i, R[u+1][i]});
}
sort(all(shit2));
shit2.resize(unique(all(shit2))-shit2.begin());
for (pii p2:shit2) if (p2.second-p2.first>1){
int pos=lower_bound(all(vec[u+1]), p2)-vec[u+1].begin();
// assert(pos<SZ(vec[u+1]) && vec[u+1][pos]==p2); // namoosan ok bash
ans+=(dwn[u+1][pos]+1>=d);
}
}
}
return ans;
}
