#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll count_rectangles(std::vector<std::vector<int>> a) {
    const int n = size(a), m = size(a[0]);
    if (n <= 2 || m <= 2) {
        return 0;
    }
    if (n == 3) {
        vector<int> aliveL, L(m, -1), good(m), stk;
        for (int i = 0; i < m; ++i) {
            good[i] = a[1][i] < a[0][i] && a[2][i] > a[1][i];
            while (!stk.empty() && a[1][stk.back()] < a[1][i]) {
                stk.pop_back();
            }
            if (!stk.empty()) {
                L[i] = stk.back();
            }
            stk.push_back(i);
        }
        ll ans = 0;
        for (int i = 1; i < m - 1; ++i) {
            aliveL.push_back(i - 1);
            while (!aliveL.empty() && a[1][aliveL.back()] <= a[1][i]) {
                aliveL.pop_back();
            }
            if (!good[i]) {
                aliveL.clear();
            }
            ans += aliveL.end() - std::lower_bound(aliveL.begin(), aliveL.end(), L[i + 1]);
        }
        return ans;
    }
	return 1;
}