#include "rect.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1e9 + 7;

struct SegmentTree {
    int R;

    vector<int> mn, mx;

    SegmentTree(vector<int> vals) {
        R = 1;
        while (R < (int)vals.size()) {
            R *= 2;
        }
        mn.assign(R * 2, inf);
        mx.assign(R * 2, -inf);
        for (int i = 0; i < (int)vals.size(); ++i) {
            mn[i + R] = mx[i + R] = vals[i];
        }
        for (int i = R - 1; i > 0; --i) {
            mn[i] = min(mn[i * 2], mn[i * 2 + 1]);
            mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
        }
    }

    pair<int, int> get(int l, int r) {
        l += R;
        r += R;
        pair<int, int> ans = make_pair(inf, -inf);
        while (l < r) {
            if (l & 1) {
                ans.first = min(ans.first, mn[l]);
                ans.second = max(ans.second, mx[l]);
                l++;
            }
            if (r & 1) {
                --r;
                ans.first = min(ans.first, mn[r]);
                ans.second = max(ans.second, mx[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
};

long long count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m));
    for (int i = 0; i < n; ++i) {
        vector<int> st;
        for (int j = 0; j < m; ++j) {
            while (!st.empty() && a[i][st.back()] <= a[i][j]) {
                right[i][st.back()] = j;
                st.pop_back();
            }
            st.push_back(j);
        }
        st.clear();
        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && a[i][st.back()] <= a[i][j]) {
                left[i][st.back()] = j;
                st.pop_back();
            }
            st.push_back(j);
        }
    }
    for (int j = 0; j < m; ++j) {
        vector<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && a[st.back()][j] <= a[i][j]) {
                down[st.back()][j] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && a[st.back()][j] <= a[i][j]) {
                up[st.back()][j] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
    }
    vector<SegmentTree> upTree, downTree, leftTree, rightTree;
    for (int i = 0; i < n; ++i) {
        upTree.emplace_back(up[i]);
        downTree.emplace_back(down[i]);
    }
    for (int j = 0; j < m; ++j) {
        vector<int> leftNw, rightNw;
        for (int i = 0; i < n; ++i) {
            leftNw.push_back(left[i][j]);
            rightNw.push_back(right[i][j]);
        }
        leftTree.emplace_back(leftNw);
        rightTree.emplace_back(rightNw);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            up[i][j] = -1;
            down[i][j] = n;
            left[i][j] = -1;
            right[i][j] = m;
        }
    }
    for (int i = 0; i < n; ++i) {
        vector<int> st;
        for (int j = 0; j < m; ++j) {
            while (!st.empty() && a[i][st.back()] < a[i][j]) {
                right[i][st.back()] = j;
                st.pop_back();
            }
            st.push_back(j);
        }
        st.clear();
        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && a[i][st.back()] < a[i][j]) {
                left[i][st.back()] = j;
                st.pop_back();
            }
            st.push_back(j);
        }
    }
    for (int j = 0; j < m; ++j) {
        vector<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && a[st.back()][j] < a[i][j]) {
                down[st.back()][j] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && a[st.back()][j] < a[i][j]) {
                up[st.back()][j] = i;
                st.pop_back();
            }
            st.push_back(i);
        }
    }
    vector<pair<pair<int, int>, pair<int, int>>> rects;
    for (int i = 1; i + 1 < n; ++i) {
        for (int j = 1; j + 1 < m; ++j) {
            if (up[i][j] != -1 && down[i][j] != n && left[i][j] != -1 && right[i][j] != m) {
                rects.emplace_back(make_pair(up[i][j], left[i][j]), make_pair(down[i][j], right[i][j]));
            }
        }
    }
    sort(rects.begin(), rects.end());
    rects.resize(unique(rects.begin(), rects.end()) - rects.begin());
    long long ans = 0;
    for (int i = 0; i < (int)rects.size(); ++i) {
        int u = rects[i].first.first, l = rects[i].first.second, d = rects[i].second.first, r = rects[i].second.second;
        if (downTree[u].get(l + 1, r).first >= d && upTree[d].get(l + 1, r).second <= u && rightTree[l].get(u + 1, d).first >= r && leftTree[r].get(u + 1, d).second <= l) {
            ans++;
        }
    }
    return ans;
}