#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
ll count_rectangles(vector<vector<int>> a) {
int n,m;
{
n=(int)a.size();
assert(n>0);
m=(int)a[0].size();
for(int i=0;i<n;i++){
assert((int)a[i].size()==m);
}
}
vector<vector<pair<int, int>>> wr(n),wc(m);
vector<vector<int>> cr(n),cc(m);
function<bool(int, pair<int, int>)> has_row=[&](int i,pair<int, int> want){
assert(0<=i&&i<n);
int l=0,r=(int)wr[i].size()-1;
while(l<=r){
int m=(l+r)/2;
if(wr[i][m]==want) return 1;
if(wr[i][m]<want) l=m+1; else r=m-1;
}
return 0;
};
for (int r=0;r<n;r++){
vector<int> stk;
for (int c=0;c<m;c++){
while(!stk.empty()&&a[r][stk.back()]<=a[r][c]) {
if(stk.back()+1<=c-1&&a[r][stk.back()]!=a[r][c]) {
wr[r].push_back({stk.back()+1, c-1});
}
stk.pop_back();
}
stk.push_back(c);
}
stk.clear();
for (int c=m-1;c>=0;c--){
while(!stk.empty()&&a[r][stk.back()]<=a[r][c]) {
if(c+1<=stk.back()-1) {
wr[r].push_back({c+1, stk.back()-1});
}
stk.pop_back();
}
stk.push_back(c);
}
stk.clear(); /// why lol? dunno
}
for (int c=0;c<m;c++){
vector<int> stk;
for (int r=0;r<n;r++){
while(!stk.empty()&&a[stk.back()][c]<=a[r][c]) {
if(stk.back()+1<=r-1&&a[stk.back()][c]!=a[r][c]) {
wc[c].push_back({stk.back()+1, r-1});
}
stk.pop_back();
}
stk.push_back(r);
}
stk.clear();
for (int r=n-1;r>=0;r--){
while(!stk.empty()&&a[stk.back()][c]<=a[r][c]) {
if(r+1<=stk.back()-1) {
wc[c].push_back({r+1, stk.back()-1});
}
stk.pop_back();
}
stk.push_back(r);
}
stk.clear(); /// why lol? dunno
}
for(auto &V:wr) sort(V.begin(),V.end());
for(auto &V:wc) sort(V.begin(),V.end());
for(int i=n-1;i>=0;i--){
cr[i].resize((int)wr[i].size(),1);
if(i<n-1){
int pt=0;
for (int j=0;j<(int)wr[i].size();j++){
while(pt<(int)wr[i+1].size()&&wr[i+1][pt]<wr[i][j]) pt++;
if(pt<(int)wr[i+1].size()&&wr[i+1][pt]==wr[i][j]){
cr[i][j]+=cr[i+1][pt];
}
}
}
}
for(int i=m-1;i>=0;i--){
cc[i].resize((int)wc[i].size(),1);
if(i<m-1){
int pt=0;
for (int j=0;j<(int)wc[i].size();j++){
while(pt<(int)wc[i+1].size()&&wc[i+1][pt]<wc[i][j]) pt++;
if(pt<(int)wc[i+1].size()&&wc[i+1][pt]==wc[i][j]){
cc[i][j]+=cc[i+1][pt];
}
}
}
}
ll sol=0;
for (int r1=1;r1<n-1;r1++){
int posr=-1;
for (auto &it:wr[r1]) {
posr++;
int c1=it.first,c2=it.second;
{
int c_smaller_or_equal=0,c_smaller=0;
{
int low=0,high=(int)wc[c1].size()-1;
while(low<=high){
int mid=(low+high)/2;
if(wc[c1][mid].first<=r1){
c_smaller_or_equal=mid+1;
low=mid+1;
}else{
high=mid-1;
}
}
}
{
int low=0,high=(int)wc[c1].size()-1;
while(low<=high){
int mid=(low+high)/2;
if(wc[c1][mid].first<r1){
c_smaller=mid+1;
low=mid+1;
}else{
high=mid-1;
}
}
}
assert(c_smaller<=c_smaller_or_equal);
if(c_smaller<c_smaller_or_equal){
for (int p=c_smaller;p<c_smaller_or_equal;p++){
auto it2=wc[c1][p];
assert(it2.first==r1);
int r2=it2.second;
if(cr[r1][posr]>=r2-r1+1&&cc[c1][p]>=c2-c1+1){
sol++;
}
}
}
}
}
}
return sol;
}
