#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);
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) {
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) {
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());
ll sol=0;
for (int r1=1;r1<n-1;r1++){
for (auto &it:wr[r1]) {
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;
bool is_ok=1;
for (int r=r1;r<=r2&&is_ok;r++){
for(int c=c1;c<=c2&&is_ok;c++){
is_ok&=(a[r][c]<a[r1-1][c]);
is_ok&=(a[r][c]<a[r2+1][c]);
is_ok&=(a[r][c]<a[r][c1-1]);
is_ok&=(a[r][c]<a[r][c2+1]);
}
}
sol+=is_ok;
}
}
}
}
}
return sol;
}
