#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector <vector <int>> a){
int n = a.size(), m = a[0].size();
vector <stack <int>> st_row(n - 1), st_col(m - 1);
for (int i = 0; i < n - 1; ++ i) st_row[i].push(0);
for (int j = 0; j < m - 1; ++ j) st_col[j].push(0);
vector <vector <int>> cnt_row(m - 1, vector <int>(m - 1)), last_row(m - 1, vector <int>(m - 1)),
cnt_col(n - 1, vector <int>(n - 1)), last_col(n - 1, vector <int>(n - 1));
vector <int> bit(n, 0);
auto update = [&](int p, int val) -> void {
for (; p < n; p += p & -p)
bit[p] += val;
};
auto get = [&](int p) -> int {
int ans = 0;
for (; p; p -= p & -p)
ans += bit[p];
return ans;
};
long long ans = 0;
for (int i = 0; i < n - 1; ++ i){
for (int j = 0; j < m - 1; ++ j){
bool ok = true;
vector <pair <int, int>> rect_row, rect_col;
while (!st_row[i].empty()){
int pj = st_row[i].top();
if (pj < j && ok){
if (last_row[pj + 1][j] < i - 1) cnt_row[pj + 1][j] = 0;
cnt_row[pj + 1][j] ++;
last_row[pj + 1][j] = i;
rect_row.emplace_back(j - pj, cnt_row[pj + 1][j]);
}
if (a[i][pj] > a[i][j + 1]) break;
st_row[i].pop();
ok &= a[i][pj] < a[i][j + 1];
}
st_row[i].push(j + 1);
ok = true;
while (!st_col[j].empty()){
int pi = st_col[j].top();
if (pi < i && ok){
if (last_col[pi + 1][i] < j - 1) cnt_col[pi + 1][i] = 0;
cnt_col[pi + 1][i] ++;
last_col[pi + 1][i] = j;
rect_col.emplace_back(cnt_col[pi + 1][i], i - pi);
}
if (a[pi][j] > a[i + 1][j]) break;
st_col[j].pop();
ok &= a[pi][j] < a[i + 1][j];
}
st_col[j].push(i + 1);
sort(rect_col.rbegin(), rect_col.rend());
reverse(rect_row.begin(), rect_row.end());
int ptr = 0;
for (auto [a, b] : rect_row){
while (ptr < rect_col.size() && rect_col[ptr].first >= a) update(rect_col[ptr ++].second, 1);
ans += get(b);
}
while (ptr --) update(rect_col[ptr].second, -1);
}
}
return ans;
}
