#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mp make_pair
using pii = pair<int,int>;
using ll = long long int;
const int N = 2.5e3 + 10;
int ans,n,m,f[N];
vector<pii> R[N][N],C[N][N];
void upd(int t, int x){
for(t+=5; t<N; t+=t&-t) f[t]+=x;
}
int get(int t, int x=0){
for(t+=5; t; t-=t&-t) x+=f[t];
return x;
}
ll count_rectangles(vector<vector<int> > A) {
n=A.size();
m=A[0].size();
for(int i=0; i<n; i++){
vector<int> st;
for(int j=0; j<m; j++){
int f=0;
while(!st.empty() && A[i][st.back()]<=A[i][j]){
if(A[i][st.back()]==A[i][j]) f=1;
if(j-st.back()>1){
R[i][st.back()+1].pb({j-1,i});
}
st.pop_back();
}
if(!f && !st.empty() && j-st.back()>1) R[i][st.back()+1].pb({j-1,i});
st.pb(j);
}
}
for(int j=0; j<m; j++){
vector<int> st;
for(int i=0; i<n; i++){
int f=0;
while(!st.empty() && A[st.back()][j]<=A[i][j]){
if(A[st.back()][j]==A[i][j]) f=1;
if(i-st.back()>1){
C[st.back()+1][j].pb({i-1,j});
}
st.pop_back();
}
if(!f && !st.empty() && i-st.back()>1) C[st.back()+1][j].pb({i-1,j});
st.pb(i);
}
}
for(int i=n-1; i--; ){
for(int j=m-1; j--; ){
for(int k=0; k<(int)R[i][j].size(); k++){
auto it=lower_bound(R[i+1][j].begin(),R[i+1][j].end(),mp(R[i][j][k].F,-1));
if(it!=R[i+1][j].end() && it->F==R[i][j][k].F) R[i][j][k].S=it->S;
}
for(int k=0; k<(int)C[i][j].size(); k++){
auto it=lower_bound(C[i][j+1].begin(),C[i][j+1].end(),mp(C[i][j][k].F,-1));
if(it!=C[i][j+1].end() && it->F==C[i][j][k].F) C[i][j][k].S=it->S;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
for(int k=0; k<(int)C[i][j].size(); k++){
upd(C[i][j][k].F,1);
}
sort(C[i][j].begin(),C[i][j].end(),[&](const pii &a, const pii &b){return a.S<b.S;});
int p=0;
for(int k=0; k<(int)R[i][j].size(); k++){
while(p<(int)C[i][j].size() && C[i][j][p].S<R[i][j][k].F){
upd(C[i][j][p].F,-1);
p++;
}
ans+=get(R[i][j][k].S);
}
while(p<(int)C[i][j].size()){
upd(C[i][j][p].F,-1);
p++;
}
}
}
return ans;
}
