#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
const int MX=2500;
int bt[MX];
void upd(int id, int val){
if(id<=0)return;
while(id<MX){
bt[id]+=val;
id+=id&(-id);
}
}
int query(int id){
int resp=0;
if(id<=0)return 0;
while(id>0){
resp+=bt[id];
id-=id&(-id);
}
return resp;
}
long long count_rectangles(std::vector<std::vector<int> > vec) {
int n=sz(vec);
int m=sz(vec[0]);
vector<vector<vector<pair<int,int>>>> line(n,vector<vector<pair<int,int>>>(m));//so pra direita
vector<vector<vector<pair<int,int>>>> col(n,vector<vector<pair<int,int>>>(m));//so pra baixo
L(i,1,n-2){//calc pra baixo na col i
vector<int> st;
L(j,0,m-1){
while(!st.empty() && vec[i][st.back()]<=vec[i][j]){
if(st.back()+1!=j)col[i][st.back()].push_back({j,i});
st.pop_back();
}
if(!st.empty()){
if(st.back()+1!=j)col[i][st.back()].push_back({j,i});
}
st.push_back(j);
}
}
L(j,1,m-2){
vector<int> st;
L(i,0,n-1){
while(!st.empty() && vec[st.back()][j]<=vec[i][j]){
if(st.back()+1!=i)line[st.back()][j].push_back({i,j});
st.pop_back();
}
if(!st.empty()){
if(st.back()+1!=i)line[st.back()][j].push_back({i,j});
}
st.push_back(i);
}
}
R(i,n-2,1){
L(j,0,m-1){
for(auto &[h,id]:col[i][j]){
auto pt=lower_bound(all(col[i+1][j]),make_pair(h,-1));
if(pt==col[i+1][j].end() || (*pt).first!=h)continue;
id=(*pt).second;
}
}
}
R(j,m-2,1){
L(i,0,n-1){
for(auto &[c,id]:line[i][j]){
auto pt=lower_bound(all(line[i][j+1]),make_pair(c,-1));
if(pt==line[i][j+1].end() || (*pt).first!=c)continue;
id=(*pt).second;
}
}
}
ll resp=0;
L(i,0,n-3){
L(j,0,m-3){
vector<pair<int,int>> C=col[i+1][j];
vector<pair<int,int>> H=line[i][j+1];
if(C.empty() || H.empty())continue;
for(auto &p:H)swap(p.first,p.second);
sort(all(H));
int ptb=0;
for(auto [h,longe]:C){
while(ptb<sz(H) && H[ptb].first<h-1){
resp+=query(MX-1)-query(H[ptb].second-2);
ptb++;
}
upd(longe,1);
}
while(ptb<sz(H)){
resp+=query(MX-1)-query(H[ptb].second-2);
ptb++;
}
for(auto [h,longe]:C){
upd(longe,-1);
}
}
}
return resp;
}
