#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int lim=3000;
struct{
int tree[lim];
void clear(){
fill(tree,tree+lim,0);
}
void update(int p,int val){
p++;
while(p<lim){
tree[p]+=val;
p+=p&-p;
}
}
int query(int p){
p++;
int ans=0;
while(p){
ans+=tree[p];
p-=p&-p;
}
return ans;
}
int query(int l,int r){
if(r<l)return 0;
return query(r)-query(l-1);
}
}fw;
long long count_rectangles(std::vector<std::vector<int> > a) {
int n=a.size();
int m=a[0].size();
if(n==3){
int l[m];
stack<int>st;
for(int i=0;i<m;i++){
while(st.size()&&a[1][st.top()]<a[1][i]){
st.pop();
}
if(st.size()){
l[i]=st.top();
}else{
l[i]=0;
}
st.push(i);
}
int r[m];
while(st.size())st.pop();
for(int i=m-1;0<=i;i--){
while(st.size()&&a[1][st.top()]<a[1][i]){
st.pop();
}
if(st.size()){
r[i]=st.top();
}else{
r[i]=m;
}
st.push(i);
}
vector<int>torem[m+5];
long int ans=0;
for(int i=0;i<m;i++){
for(int j:torem[i]){
//cerr<<"removed "<<j<<" at "<<i<<"\n";
fw.update(j,-1);
}
if(1<i&&l[i]<=i-2){
int k=fw.query(l[i],i-2);
//cerr<<"queried "<<l[i]<<" "<<i-2<<"\n";
//cerr<<k<<"\n";
ans+=k;
}
if(a[1][i]>=a[0][i]||a[1][i]>=a[2][i]){
//cerr<<"clear at "<<i<<"\n";
fw.clear();
for(int j=i;j<m;j++){
torem[j].clear();
}
}
fw.update(i,1);
torem[r[i]+1].push_back(i);
}
return ans;
}
return -1;
}
