#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "rect.h"
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
const int N=25e2;
vector<int> st;
vector<pair<int,int>> r[N+10][N+10];
vector<pair<int,int>> u[N+10][N+10];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
long long count_rectangles(vector<vector<int>> a)
{
int n=a.size(),m=a[0].size();
long long ans=0;
for(int i=1;i<n-1;i++)
{
st.clear();
for(int j=0;j<m;j++)
{
while(!st.empty() && a[i][st.back()]<a[i][j])
{
if(st.back()+1<=j-1)
r[i][st.back()+1].emplace_back(j-1,1);
st.pop_back();
}
if(!st.empty() && st.back()+1<=j-1)
r[i][st.back()+1].emplace_back(j-1,1);
st.push_back(j);
}
}
for(int j=1;j<m-1;j++)
{
st.clear();
for(int i=0;i<n;i++)
{
while(!st.empty() && a[st.back()][j]<a[i][j])
{
if(st.back()+1<=i-1)
u[st.back()+1][j].emplace_back(i-1,1);
st.pop_back();
}
if(!st.empty() && st.back()+1<=i-1)
u[st.back()+1][j].emplace_back(i-1,1);
st.push_back(i);
}
}
for(int i=n-2;i>=1;i--)
{
for(int j=0;j<m;j++)
{
size_t it=0;
for(auto &v:r[i][j])
{
while(it<r[i+1][j].size() && r[i+1][j][it].fi<v.fi)
it++;
if(it<r[i+1][j].size() && r[i+1][j][it].fi==v.fi)
v.se=r[i+1][j][it].se+1;
//cerr<<"r["<<i<<"]["<<j<<"]: ("<<v.fi<<","<<v.se<<")\n";
}
}
}
for(int j=m-2;j>=1;j--)
{
for(int i=0;i<n;i++)
{
size_t it=0;
for(auto &v:u[i][j])
{
while(it<u[i][j+1].size() && u[i][j+1][it].fi<v.fi)
it++;
if(it<u[i][j+1].size() && u[i][j+1][it].fi==v.fi)
v.se=u[i][j+1][it].se+1;
//cerr<<"u["<<i<<"]["<<j<<"]: ("<<v.fi<<","<<v.se<<")\n";
}
}
}
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
for(auto &v:r[i][j])
v.fi-=j-1;
for(auto &v:u[i][j])
v.fi-=i-1;
}
}
for(int i=1;i<n-1;i++)
{
for(int j=1;j<m-1;j++)
{
os.clear();
sort(u[i][j].begin(),u[i][j].end(),
[](pair<int,int> &a,pair<int,int> &b){ return a.se<b.se; });
for(int it1=(int)r[i][j].size()-1,it2=(int)u[i][j].size()-1;it1>=0;it1--)
{
while(it2>=0 && u[i][j][it2].se>=r[i][j][it1].fi)
{
os.insert(u[i][j][it2].fi);
it2--;
}
ans+=os.order_of_key(r[i][j][it1].se+1);
}
//cerr<<i<<" "<<j<<" "<<ans<<"\n";
}
}
return ans;
}
