#pragma GCC optimize("unroll-loops,Ofast")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
struct Fenwick{
vector<ll> tr;
ll n, offs;
Fenwick(ll N){
n=N+20; offs=10;
tr.resize(n+1);
}
void add(ll i, ll x){
i+=offs;
for (; i; i-=(-i&i)) tr[i]+=x;
}
ll get(ll i){
ll res=0; i+=offs;
for (; i<=n; i+=(-i&i)) res+=tr[i];
return res;
}
};
long long count_rectangles(vector<vector<int>> a) {
ll n=a.size(), m=a[0].size();
vector cols(m, vector(n, vector(n, false)));
vector rows(n, vector(m, vector(m, false)));
for (ll j=1; j<m-1; j++){
for (ll up=1; up<n-1; up++){
int cmx=a[up][j];
for (ll down=up; down<n-1; down++){
cmx=max(cmx, a[down][j]);
if (cmx<a[up-1][j] and cmx<a[down+1][j]){
cols[j][up][down]=1;
}
}
}
}
vector leftw(m, vector(n, vector(n, 0ll)));
for (ll j=1; j<m-1; j++){
for (ll up=1; up<n-1; up++){
for (ll down=up; down<n-1; down++){
leftw[j][up][down]=(cols[j][up][down]?leftw[j-1][up][down]+1:0);
}
}
}
for (ll i=1; i<n-1; i++){
for (ll l=1; l<m-1; l++){
int cmx=a[i][l];
for (ll r=l; r<m-1; r++){
cmx=max(cmx, a[i][r]);
if (cmx<a[i][l-1] and cmx<a[i][r+1]){
rows[i][l][r]=1;
}
}
}
}
vector upw(n, vector(m, vector(m, 0ll)));
for (ll i=1; i<n-1; i++){
for (ll l=1; l<m-1; l++){
for (ll r=l; r<m-1; r++){
upw[i][l][r]=(rows[i][l][r]?upw[i-1][l][r]+1:0);
}
}
}
ll cnt=0;
for (ll right=1; right<m-1; right++){
for (ll down=1; down<n-1; down++){
vector<array<ll, 2>> posb;
Fenwick gres(m);
for (ll left=right; left>=1; left--){
posb.push_back({upw[down][left][right], left});
gres.add(left, 1);
}
sort(posb.rbegin(), posb.rend());
for (ll up=down; up>=1; up--){
ll l=right-leftw[right][up][down]+1;
while (!posb.empty() and posb.back()[0]<down-up+1){
gres.add(posb.back()[1], -1);
posb.pop_back();
}
cnt+=gres.get(l);
}
}
}
// for (ll up=1; up<n-1; up++){
// for (ll down=up; down<n-1; down++){
// for (ll r=1; r<m-1; r++){
// for (ll l=r; l>=1; l--){
// if (!cols[l][up][down]){
// break;
// }
// if (upw[down][l][r]>=(down-up+1)) {
// cnt++;
// }
// }
// }
// }
// }
return cnt;
}
