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

using namespace std;
using ll = long long;

void ckmax(int &x, int y) {
    if (x < y) {
        x = y;
    }
}

void ckmin(int &x, int y) {
    if (x > y) {
        x = y;
    }
}

constexpr int maxN = 2500 + 7;

vector<int> queries[maxN];

namespace Fenwick {
    int a[maxN];
    void add(int x) {
        for (++x; x < maxN; x += x & -x) {
            ++a[x];
        }
    }
    int sum(int x) {
        int ans = 0;
        for (++x; x > 0; x -= x & -x) {
            ans += a[x];
        }
        return ans;
    }
}

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;
    }

    vector LA(n, vector<int>(m, 0)), RA(n, vector<int>(m, m - 1));

    for (int i = 1; i + 1 < n; ++i) {
        vector<int> stk;
        for (int j = 0; j < m; ++j) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty()) {
                LA[i][j] = stk.back();
            }
            stk.push_back(j);
        }
        stk.clear();
        for (int j = m - 1; j >= 0; --j) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            if (!stk.empty()) {
                RA[i][j] = stk.back();
            }
            stk.push_back(j);
        }
    }

    vector<int> maxL(m, 0), minR(m, m - 1), mx(m), L(maxL), R(minR);
    vector<bool> good(m);
    ll ans = 0;

    auto solve = [&]() {
        memset(Fenwick::a, 0, sizeof(Fenwick::a));
        for (int i = 0; i < m; ++i) {
            queries[i].clear();
        }
        for (int i = 0; i < m; ++i) {
            queries[L[i]].push_back(i);
//            cout << L[i] << " ";
        }
//        cout << endl;
        for (int l = 0; l < m - 1; ++l) {
//            cout << R[l] << " ";
            for (int r : queries[l]) {
                Fenwick::add(r);
            }
            ans += Fenwick::sum(R[l]) - (l + 2);
        }
//        cout << endl;
    };

    for (int i = 1; i + 1 < n; ++i) {
        fill(mx.begin(), mx.end(), -1);
        fill(good.begin(), good.end(), true);

        for (int j = i; j + 1 < n; ++j) {
            for (int k = 0, mxNotGood = -1; k < m; ++k) {
                ckmax(mx[k], a[j][k]);
                ckmax(maxL[k], LA[j][k]);
                ckmin(minR[k], RA[j][k]);
                L[k] = max(mxNotGood, maxL[k]);
                if (mx[k] >= min(a[i + 1][k], a[i - 1][k])) {
                    good[k] = false;
                    mxNotGood = k;
                }
            }
            for (int k = m - 1, mnNotGood = m; k >= 0; --k) {
                R[k] = min(minR[k], mnNotGood);
                if (!good[k]) {
                    mnNotGood = k;
                }
            }
            solve();
        }
    }

    return ans;
}