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