#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
if (n < 3){
return 0;
}
assert(n == 3);
vector<bool> c(m);
for (int i = 0; i < m; i++){
c[i] = a[0][i] > a[1][i] && a[2][i] > a[1][i];
}
vector<int> S(m + 1);
S[0] = 0;
for (int i = 0; i < m; i++){
S[i + 1] = S[i];
if (!c[i]){
S[i + 1]++;
}
}
map<int, vector<int>> mp;
for (int j = 0; j < m; j++){
mp[a[1][j]].push_back(j);
}
set<int> st = {-1, m};
set<pair<int, int>> ans;
for (auto itr = mp.rbegin(); itr != mp.rend(); itr++){
vector<int> id = (*itr).second;
for (int i : id){
if (i > 0 && i < m - 1){
int L = *prev(st.lower_bound(i)) + 1;
int R = *st.lower_bound(i);
if (0 < L && R < m){
if (S[R] - S[L] == 0){
ans.insert(make_pair(L, R));
}
}
}
}
for (int i : id){
st.insert(i);
}
}
return ans.size();
}
