#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, m;
bool valid(int x, int y) {
if (x >= 0 && x<n && y >= 0 && y < m) return true;
else return false;
}
struct SegTree {
vector<int> tree;
SegTree(int n) {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l==r && l==i) {
tree[p] = x;
}
else {
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
tree[p] = max(tree[2*p], tree[2*p+1]);
}
}
int rmq(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i<=l && r <= j) {
return tree[p];
}
int m = (l+r)/2;
int i1 = rmq(2*p, l, m, i, j);
int i2 = rmq(2*p+1, m+1, r, i, j);
return max(i1, i2);
}
};
ll count_rectangles(vector<vector<int>> a) {
n = a.size();
if (n <= 2) return 0;
m = a[0].size();
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
vector<vector<bool>> vis(n, vector<bool>(m, false));
/*vector<vector<int>> rows(n, vector<int>(m, 0));
for (int i=0; i<n; i++) {
rows[i][0] = a[i][0];
for (int j=1; j<m; j++) {
rows[i][j] = rows[i][j-1] + a[i][j];
}
}
vector<vector<int>> col(m, vector<int>(n, 0));
for (int i=0; i<m; i++) {
col[i][0] = a[0][i];
for (int j=1; j<n; j++) {
col[i][j] = a[j][i] + col[i][j-1];
}
}*/
vector<int> pref(m, 0);
vector<int> b(m);
for (int i=0; i<m; i++) {
b[i] = (a[1][i] < a[0][i] && a[1][i] < a[2][i]);
}
ll cnt=0;
SegTree st(m);
for (int i=0; i<m; i++) {
st.query(1, 0, m-1, i, a[1][i]);
}
for (int i=1; i<m-1; i++) {
int mx=0;
int mn = b[i];
for (int j=i; j<m-1; j++) {
mx = max(mx, a[1][j]);
mn = min(mn, b[j]);
if (mn == 0) break;
if (mx < a[1][i-1] && mx < a[1][j+1]) {
cnt++;
}
}
}
return cnt;
}
