#include "rect.h"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>

std::vector<std::pair<int, int>> get_cum(const std::vector<int>& vec) {
    int n = vec.size();
    std::vector<int> stack;
    std::vector<std::pair<int, int>> res;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && vec[stack.back()] <= vec[i]) {
            if (stack.size() > 1 && vec[stack.back()] < vec[i]) {
                res.push_back({stack.rbegin()[1] + 1, i - 1});
            }
            stack.pop_back();
        }
        stack.push_back(i);
    }
    std::sort(res.begin(), res.end());
    // // res.clear();
    // for (int i = 0; i < n; i++) {
    //     int mx = 0;
    //     for (int j = i; j < n; j++) {
    //         bool suc = i != 0 && j != n - 1;
    //         mx = std::max(mx, vec[j]);
    //         if (suc) {
    //             suc = mx < std::min(vec[i - 1], vec[j + 1]);
    //         }
    //         // if (suc) {
    //         //     res.push_back({i, j});
    //         // }
    //         // if (suc)
    //         assert(suc == std::binary_search(res.begin(), res.end(), std::pair<int, int>{i, j}));
    //     }
    // }

    // return std::move(res);
    return res;
}

uint32_t hash(const std::pair<int, int> p) {
    return (p.first << 16) + p.second;
}

long long count_rectangles(std::vector<std::vector<int>> a) {
    // {
    //     std::mt19937 rnd;
    //     int n = 50;
    //     std::vector<int> vec(n);
    //     while (true) {
    //         for (int& i : vec) {
    //             i = rnd() % 5;
    //         }
    //         auto p = get_cum(vec);
    //     }
    // }
    // return 0;
    int n = a.size();
    int m = a[0].size();
    std::vector<std::vector<int>> t_a(m, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            t_a[j][i] = a[i][j];
        }
    }

    std::vector<std::vector<std::pair<int, int>>> r(n), c(m);
    for (int i = 0; i < n; i++) {
        r[i] = get_cum(a[i]);
    }
    for (int i = 0; i < m; i++) {
        c[i] = get_cum(t_a[i]);
    }

    int ans = 0;
    for (int i1 = 1; i1 < n - 1; i1++) {
        for (int j1 = 1; j1 < m - 1; j1++) {
            for (int i2 = i1; i2 < n - 1; i2++) {
                for (int j2 = j1; j2 < m - 1; j2++) {
                    bool fck = false;
                    for (int i = i1; i <= i2; i++) {
                        if (!std::binary_search(r[i].begin(), r[i].end(), std::pair<int, int>{j1, j2})) {
                            fck = true;
                            break;
                        }
                    }
                    for (int j = j1; !fck && j <= j2; j++) {
                        if (!std::binary_search(c[j].begin(), c[j].end(), std::pair<int, int>{i1, i2})) {
                            fck = true;
                            break;
                        }
                    }
                    if (!fck) {
                        ans++;
                        // std::cerr << i1 << " " << j1 << "  " << i2 << " " << j2 << "\n";
                    }
                }
            }
        }
    }

    return ans;
    // auto fuck = [&](auto fuck, int l, int r) {
    //     int m = (l + r) / 2;
    // };
}