#include "bits/stdc++.h"
#include "rect.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("{" + string(#args) + "}", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int lft[2505][2505];
int rht[2505][2505];
vector<pair<int, int>> interval[2505];
vector<pair<int, int>> otherrow[2505][2505];
struct segment {
int l, r, last;
bool operator<(segment o) const {
return l < o.l;
}
};
vector<segment> row[2505];
int bit[2505][2505];
void update(int id, int pos, int val) {
for (; pos < 2505; pos += pos & -pos) {
bit[id][pos] += val;
}
}
int query(int id, int pos) {
int sum = 0;
for (; pos; pos -= pos & -pos) {
sum += bit[id][pos];
}
return sum;
}
ll count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m= a[0].size();
if (min(n, m) <= 2) {
return 0;
}
deque<int> dq;
memset(lft, -1, sizeof(lft));
memset(rht, -1, sizeof(rht));
for (int i = 1; i <= n - 2; i++) {
while (!dq.empty()) dq.pop_back();
for (int j = 0; j < m; j++) {
while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back();
if (!dq.empty() && dq.back() != j-1) {
lft[i][j] = dq.back();
interval[i].push_back({dq.back(), j});
}
dq.push_back(j);
}
while (!dq.empty()) dq.pop_back();
for (int j = m - 1; j >= 0; j--) {
while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back();
if (!dq.empty() && dq.back() != j+1) {
rht[i][j] = dq.back();
interval[i].push_back({j, dq.back()});
}
dq.push_back(j);
}
}
for (int i = 1; i <= n-2; i++) {
for (auto [l, r] : interval[i]) {
if (lft[i][r] != l && rht[i][l] != r) continue;
if (lft[i][r] == l) lft[i][r] = -1;
if (rht[i][l] == r) rht[i][l] = -1;
int nxt = i + 1;
while (nxt <= n - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) {
if (lft[nxt][r] == l) lft[nxt][r] = -1;
if (rht[nxt][l] == r) rht[nxt][l] = -1;
nxt++;
}
for (int j = i; j < nxt; j++) {
row[j].push_back({l + 1, r - 1, nxt - 1});
}
}
sort(row[i].begin(), row[i].end());
}
memset(lft,-1,sizeof(lft));
memset(rht,-1,sizeof(rht));
for (int i = 1; i <= m - 2; i++) {
while (!dq.empty()) dq.pop_back();
for (int j = 0; j < n; j++) {
while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back();
if (!dq.empty() && dq.back() != j-1) {
lft[i][j] = dq.back();
interval[i].push_back({dq.back(), j});
}
dq.push_back(j);
}
while (!dq.empty()) dq.pop_back();
for (int j = n - 1; j >= 0; j--) {
while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back();
if (!dq.empty() && dq.back() != j+1) {
rht[i][j] = dq.back();
interval[i].push_back({j, dq.back()});
}
dq.push_back(j);
}
}
for (int i = 1; i <= m - 2; i++) {
for (auto [l, r] : interval[i]) {
if (lft[i][r] != l && rht[i][l] != r) continue;
if (lft[i][r] == l) lft[i][r] = -1;
if (rht[i][l] == r) rht[i][l] = -1;
int nxt = i + 1;
while (nxt <= m - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) {
if (lft[nxt][r] == l) lft[nxt][r] = -1;
if (rht[nxt][l] == r) rht[nxt][l] = -1;
nxt++;
}
for (int j = i; j < nxt; j++) {
otherrow[l + 1][i].emplace_back(j, r - 1);
}
}
}
ll ans = 0;
for (int i = 1; i <= n - 2; i++) {
int cur = 1;
vector<pair<int, int>> ops;
for (auto [l, r, last] : row[i]) {
while (cur <= l) {
for (auto [col, lastrow] : otherrow[i][cur]) {
update(col, lastrow, 1);
ops.push_back({col, lastrow});
}
cur++;
}
ans += query(r, last);
}
while (!ops.empty()) {
auto [col, lastrow] = ops.back();
ops.pop_back();
update(col, lastrow, -1);
}
}
return ans;
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//// freopen("", "r", stdin);
//// freopen("", "w", stdout);
// cout << count_rectangles({{4, 8, 7, 5, 6},
// {7, 4, 10, 3, 5},
// {9, 7, 20, 14, 2},
// {9, 14, 7, 3, 6},
// {5, 7, 5, 2, 7},
// {4, 5, 13, 5, 6}});
//}
