#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()][r]<=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
}
ll sol=0;
for (int r1=1;r1<n-1;r1++){
for (auto &it:wr[r1]) {
int c1=it.first,c2=it.second;
for(auto&it2:wc[c1]){
if(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;
}
