#pragma GCC optimize("Ofast","unroll-loops")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
long long ans = 0;
for(int i=0;i<m;i++) {
vector<int> maxi(n);
vector<bool> allowedrow(n);
vector allowedranges(n,vector(n,0));
for(int j=i+1;j<m-1;j++) {
for(int k=0;k<n;k++) {
maxi[k]=max(maxi[k],a[k][j]);
allowedrow[k]=maxi[k]<a[k][i] and maxi[k]<a[k][j+1];
}
const int tar = j-i;
{
stack<pair<int,int>> s;
int last_voilater = -1;
for(int k=0;k<n;k++) {
if(k!=0 and !allowedrow[k-1])last_voilater=k-1;
while(!s.empty() and s.top().first<a[k][j])s.pop();
if(s.empty()) {
s.emplace(a[k][j],k);
continue;
}
int l = s.top().second;l++;
s.emplace(a[k][j],k);
int r = s.top().second;r--;
if(r<l)continue;
allowedranges[l][r]++;
if(l<=last_voilater)continue;
if(allowedranges[l][r]==tar)ans++;
}
}
{
stack<pair<int,int>> s;
int last_voilater = n;
for(int k=n-1;k>=0;k--){
if(k!=n-1 and !allowedrow[k+1])last_voilater=k+1;
while(!s.empty() and s.top().first<a[k][j])s.pop();
if(s.empty() or s.top().first==a[k][j]) {
s.emplace(a[k][j],k);
continue;
}
int r = s.top().second;r--;
s.emplace(a[k][j],k);
int l = s.top().second;l++;
if(r<l)continue;
allowedranges[l][r]++;
if(last_voilater<=r)continue;
if(allowedranges[l][r]==tar)ans++;
}
}
}
}
return ans;
}
