#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
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 u=1; u<n; u++) for (int d=u+2; d<=n; d++)
for (int l=1; l<m; l++) for (int r=l+2; r<=m; r++){
int ok=1;
for (int i=l+1; i<r; i++) ok&=(U[d][i]==u || D[u][i]==d);
for (int i=u+1; i<d; i++) ok&=(R[i][l]==r || L[i][r]==l);
ans+=ok;
}
return ans;
}
