#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll count_rectangles(vector<vector<int>> a) {
int n = (int) a.size(), m = (int) a[0].size();
vector<vector<int>> cp(n, vector<int>(m, -1)), cn(n, vector<int>(m, -1));
vector<vector<int>> rp(n, vector<int>(m, -1)), rn(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
stack<int> s;
for (int j = 0; j < m; j++) {
while (!s.empty() && a[i][j] > a[i][s.top()])
cn[i][s.top()] = j, s.pop();
if (!s.empty())
cp[i][j] = a[i][j] < a[i][s.top()] ? s.top() : cp[i][s.top()];
s.push(j);
}
}
for (int j = 0; j < m; j++) {
stack<int> s;
for (int i = 0; i < n; i++) {
while (!s.empty() && a[i][j] > a[s.top()][j])
rn[s.top()][j] = i, s.pop();
if (!s.empty())
rp[i][j] = a[i][j] < a[s.top()][j] ? s.top() : rp[s.top()][j];
s.push(i);
}
}
vector<vector<bool>> valid(n, vector<bool>(m, true));
vector<int> cpr(m * m), cpl(m * m, -2), rpc(n * n, -2), rpl(n * n, -2);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = cp[i][j] * m + cn[i][j];
if (cpl[x] < i - 1)
cpr[x] = i;
cpl[x] = i;
valid[i][j] = valid[i][j] && cpr[x] <= rp[i][j] + 1;
}
for (int j = 0; j < m; j++)
for (int i = 0; i < n; i++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = rp[i][j] * n + rn[i][j];
if (rpl[x] < j - 1)
rpc[x] = j;
rpl[x] = j;
valid[i][j] = valid[i][j] && rpc[x] <= cp[i][j] + 1;
}
cpl.assign(m * m, n + 1);
rpl.assign(n * n, m + 1);
for (int i = n - 1; i >= 0; i--)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = cp[i][j] * m + cn[i][j];
if (cpl[x] > i + 1)
cpr[x] = i;
cpl[x] = i;
valid[i][j] = valid[i][j] && cpr[x] >= rn[i][j] - 1;
}
for (int j = m - 1; j >= 0; j--)
for (int i = 0; i < n; i++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
int x = rp[i][j] * n + rn[i][j];
if (rpl[x] > j + 1)
rpc[x] = j;
rpl[x] = j;
valid[i][j] = valid[i][j] && rpc[x] >= cn[i][j] - 1;
}
int res = 0;
unordered_set<ll> rect;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1 && valid[i][j]) {
ll x = ((ll) (cp[i][j] * m + cn[i][j]) * n + rp[i][j]) * n + rn[i][j];
if (rect.find(x) == rect.end())
res++, rect.insert(x);
}
return res;
}
// int main() {
// int n = 2500, m = 2500;
// vector<vector<int>> a(n, vector<int>(m));
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)
// a[i][j] = max(i, n - i) + max(j, m - j);
// cout << count_rectangles(a) << "\n";
// }
