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

using namespace std;
using ll = long long;

namespace SparseTable {
    vector<vector<int>> mn;

    void init(const vector<int> &a) {
        int n = size(a), l = __lg(n) + !!(n & (n - 1));
        mn.resize(l);
        mn[0] = a;
        for (int k = 1; k < l; ++k) {
            mn[k].resize(n - (1 << k) + 1);
            for (int i = 0; i < size(mn[i]); ++i) {
                mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << k - 1)]);
            }
        }
    }

    int rangeMin(int l, int r) {
        int lg = __lg(r - l);
        return min(mn[lg][l], mn[lg][r - (1 << lg)]);
    }
}

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));
    vector UP(n, vector<int>(m, 0)), DOWN(n, vector<int>(m, n - 1));
    vector<array<int, 4>> rect;

    for (int t = 1; t >= 0; --t) {
        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] + t) {
                    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] + t) {
                    stk.pop_back();
                }
                if (!stk.empty()) {
                    RA[i][j] = stk.back();
                }
                stk.push_back(j);
            }
        }

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

        if (t == 1) {
            for (int i = 1; i + 1 < n; ++i) {
                for (int j = 1; j + 1 < m; ++j) {
                    rect.push_back({UP[i][j], LA[i][j], DOWN[i][j], RA[i][j]});
                }
            }
        }
    }

    sort(rect.begin(), rect.end());
    rect.resize(unique(rect.begin(), rect.end()) - rect.begin());

    int s = size(rect);
    vector<int> alright(s, 1); // 0 - left (=> min), 1 - up (=> min), 2 - right, 3 - down

    vector<vector<array<int, 4>>> rows(n), columns(m);

    for (int i = 0; i < s; ++i) {
        auto [x1, y1, x2, y2] = rect[i];
        rows[x1].push_back({y1 + 1, y2, 1, i});
        rows[x2].push_back({y1 + 1, y2, 3, i});
        columns[y1].push_back({x1 + 1, x2, 0, i});
        columns[y2].push_back({x1 + 1, x2, 2, i});
    }

    for (int i = 0; i < n; ++i) {
        SparseTable::init(DOWN[i]);
        for (auto [l, r, type, id] : rows[i]) {
            if (type == 1) {
                int got = SparseTable::rangeMin(l, r);
                alright[i] &= got >= rect[id][3];
            }
        }
        vector<int> init(UP[i]);
        for (int &x : init) {
            x = -x;
        }
        SparseTable::init(init);
        for (auto [l, r, type, id] : rows[i]) {
            if (type == 3) {
                int got = -SparseTable::rangeMin(l, r);
                alright[i] &= got <= rect[id][1];
            }
        }
    }

    for (int j = 0; j < m; ++j) {
        vector<int> init(n);
        for (int i = 0; i < n; ++i) {
            init[i] = RA[i][j];
        }
        SparseTable::init(init);
        for (auto [l, r, type, id] : columns[j]) {
            if (type == 0) {
                int got = SparseTable::rangeMin(l, r);
                alright[id] &= got >= rect[id][2];
            }
        }
        for (int i = 0; i < n; ++i) {
            init[i] = -LA[i][j];
        }
        for (auto [l, r, type, id] : columns[j]) {
            if (type == 2) {
                int got = -SparseTable::rangeMin(l, r);
                alright[id] &= got <= rect[id][0];
            }
        }
    }

    int ans = accumulate(alright.begin(), alright.end(), 0);
    return ans;
}