#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define N 805
using namespace std;
deque<int>can[N][N];
int arr[N][N],n,m,mx[N];
void build(){
for (int i=0;i<n;i++){
vector<int>st;
st.push_back(0);
for (int j=1;j<m;j++){
int last=0;
while (!st.empty()&&arr[i][st.back()]<arr[i][j]){
int p1=st.back(); st.pop_back();
if (j-p1>=2&&last<arr[i][j]&&last<arr[i][p1])
can[i][p1].push_back(j);
if (!st.empty()&&p1-st.back()>=2)
can[i][st.back()].push_back(p1);
last=max(last,arr[i][p1]);
}
st.push_back(j);
}
while (!st.empty()){
int p1=st.back(); st.pop_back();
if (!st.empty()&&p1-st.back()>=2)
can[i][st.back()].push_back(p1);
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=a.size(); m=a[0].size();
ll ans=0;
for (int i=0;i<n;i++){
for (int j=0;j<m;j++)
arr[i][j]=a[i][j];
}
build();
for (int i=1;i<n-1;i++){
for (int j=0;j<m;j++){
// cout<<i<<" "<<j<<" size "<<can[i][j].size()<<'\n';
while (!can[i][j].empty()){
int nxt=can[i][j].front();
for (int k=j;k<nxt;k++) mx[k]=0;
for (int k=i;k<n-1;k++){
if (can[k][j].empty()||can[k][j].front()!=nxt)
break;
int add=1;
for (int l=j+1;l<nxt;l++){
mx[l]=max(mx[l],arr[k][l]);
if (mx[l]>=arr[i-1][l]){
add=-1;
break;
}
if (mx[l]>=arr[k+1][l])
add=0;
}
if (add==-1) break;
// cout<<"add "<<i<<" "<<j<<" to "<<k<<" "<<nxt<<" -> "<<add<<'\n';
ans+=add;
}
// cout<<"after "<<i<<" "<<j<<"~"<<nxt<<" is "<<ans<<'\n';
can[i][j].pop_front();
}
}
}
return ans;
}
/*
4 4
10 8 7 6
9 4 4 5
8 2 6 2
3 8 9 10
*/
