#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int maxl=12;
struct BIT{
int n;
vector<int> bit;
BIT(int N):n(N){
bit.assign(n+1,0);
}
void update(int x,int val){
for(int i=x;i<=n;i+=(i&(-i))) bit[i]+=val;
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
return res;
}
};
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
long long count_rectangles(std::vector<std::vector<int> > a) {
int n=(int)a.size(),m=(int)a[0].size();
vector<vector<vector<int>>> pos(m,vector<vector<int>>(m,vector<int>()));
for(int i=1;i<n-1;i++){
vector<int> l(m),r(m),v;
for(int j=0;j<m;j++){
while(!v.empty() && a[i][v.back()]<=a[i][j]) v.pop_back();
if(!v.empty()) l[j]=v.back();
else l[j]=-1;
v.push_back(j);
}
v.clear();
for(int j=m-1;j>=0;j--){
while(!v.empty() && a[i][v.back()]<=a[i][j]) v.pop_back();
if(!v.empty()) r[j]=v.back();
else r[j]=m;
v.push_back(j);
}
for(int j=0;j<m;j++){
if(l[j]>=0 && r[j]<m){
int lt=l[j]+1,rt=r[j]-1;
if(pos[lt][rt].empty() || pos[lt][rt].back()!=i) pos[lt][rt].push_back(i);
}
}
}
vector<int> lg2(m+1,0);
for(int i=2;i<=m;i++) lg2[i]=lg2[i/2]+1;
vector<vector<vector<int>>> down(n,vector<vector<int>>(m,vector<int>(maxl,0))),up(n,vector<vector<int>>(m,vector<int>(maxl,0)));
for(int i=0;i<m;i++){
vector<int> v={0};
for(int j=1;j<n;j++){
while(!v.empty() && a[j][i]>a[v.back()][i]) v.pop_back();
if(v.empty()) up[j-1][i][0]=0;
else up[j-1][i][0]=v.back()+1;
v.push_back(j);
}
v={n-1};
for(int j=n-2;j>=0;j--){
while(!v.empty() && a[j][i]>a[v.back()][i]) v.pop_back();
if(v.empty()) down[j+1][i][0]=n-1;
else down[j+1][i][0]=v.back()-1;
v.push_back(j);
}
}
/*
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) cout << down[i][j][0] << ' ';
cout << '\n';
}
*/
for(int k=1;k<maxl;k++){
for(int i=0;i<n;i++){
for(int j=0;j<=m-(1<<k);j++){
up[i][j][k]=max(up[i][j][k-1],up[i][j+(1<<(k-1))][k-1]);
down[i][j][k]=min(down[i][j][k-1],down[i][j+(1<<(k-1))][k-1]);
}
}
}
auto Min_down = [&](int x,int l,int r){
int p=lg2[r-l+1];
return min(down[x][l][p],down[x][r-(1<<p)+1][p]);
};
auto Max_up = [&](int x,int l,int r){
int p=lg2[r-l+1];
return max(up[x][l][p],up[x][r-(1<<p)+1][p]);
};
long long ans=0;
vector<vector<int>> lst(n,vector<int>());
BIT bit(n);
auto cal = [&](int l,int r,vector<int> cur){
int cnt=0,Max=cur.back(),Min=cur.front();
//cout << '*' << l << ' ' << r << '\n';
for(int id:cur){
int rt=min(Max,Min_down(id,l,r)),lt=max(Min,Max_up(id,l,r));
//cout << id << ' ' << lt << ' ' << rt << '\n';
lst[rt+1].push_back(id);
bit.update(id,1);cnt++;
for(int x:lst[id]) bit.update(x,-1),cnt--;
ans+=cnt-bit.query(lt-1);
}
for(int x:lst[Max+1]) bit.update(x,-1);
for(int i=Min;i<=Max+1;i++) lst[i].clear();
//cout << ans << '\n';
};
for(int l=1;l<m-1;l++){
for(int r=l;r<m-1;r++){
if(pos[l][r].empty()) continue;
vector<int> cur;
for(int id:pos[l][r]){
if(cur.empty() || cur.back()+1==id) cur.push_back(id);
else cal(l,r,cur),cur={id};
}
if(!cur.empty()) cal(l,r,cur);
}
}
return ans;
}
