#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>>> on_r(n);
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) {
on_r[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) {
on_r[r].push_back({c+1, stk.back()-1});
}
stk.pop_back();
}
stk.push_back(c);
}
stk.clear(); /// why lol? dunno
}
ll sol=0;
for (int r1=1;r1<n-1;r1++){
for(int r2=r1;r2<n-1;r2++){
for (auto &it:on_r[r1]) {
int c1=it.first,c2=it.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;
}
