#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
long long count_rectangles(std::vector<std::vector<int> > v) {
ll n=v.size(),m=v[0].size();
vvvp tate(m,vvp(m)),yoko(n,vvp(n));
vvi rv(m,vi(n));
rep(i,n)rep(j,m)rv[j][i]=v[i][j];
REP(i,1,n-1){
vi st;
vi l(m,-1),r(m,m);
rep(j,m){
while(st.size()&&v[i][st.back()]<v[i][j]){
r[st.back()]=j;st.pop_back();
}
if(st.size())l[j]=st.back();
st.pb(j);
}
/*
vp srt;
rep(j,m)srt.pb(v[i][j],j);
rsort(srt);
set<ll> S;
for(auto x:srt){
auto itr=S.insert(x.se).fi;
if(itr==S.begin())continue;
itr--;
ll l=*itr;
itr++;itr++;
if(itr==S.end())continue;
ll r=*itr;
*/
REP(j,1,m-1)if(l[j]!=-1&&r[j]!=m){
if(v[i][l[j]]>v[i][j]&&v[i][r[j]]>v[i][j]){
if(tate[l[j]+1][r[j]-1].size()==0||tate[l[j]+1][r[j]-1].back().se!=i-1)tate[l[j]+1][r[j]-1].pb(i,i);
else tate[l[j]+1][r[j]-1].back().se++;
}
}
}
REP(i,1,m-1){
vp srt;
rep(j,n)srt.pb(v[j][i],j);
rsort(srt);
set<ll> S;
for(auto x:srt){
auto itr=S.insert(x.se).fi;
if(itr==S.begin())continue;
itr--;
ll l=*itr;
itr++;itr++;
if(itr==S.end())continue;
ll r=*itr;
if(v[l][i]>x.fi&&v[r][i]>x.fi){
if(yoko[l+1][r-1].size()==0||yoko[l+1][r-1].back().se!=i-1)yoko[l+1][r-1].pb(i,i);
else yoko[l+1][r-1].back().se++;
}
}
}
vvvp tmp(n,vvp(m));
rep(l,n)rep(r,n)for(auto rng:yoko[l][r]){
REP(i,rng.fi,rng.se+1)tmp[l][i].pb(r,rng.se);
}
ll ans=0;
rep(l,m)rep(r,m)for(auto rng:tate[l][r]){
REP(i,rng.fi,rng.se+1){
for(auto x:tmp[i][l]){
if(x.fi>rng.se)break;
if(x.se>=r)ans++;
}
}
}
return ans;
}
