#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
using ll = long long;
using pii = pair<int, int>;
vector<vector<int>> good_pairs(vector<int> row) {
vector<vector<int>> P(row.size());
stack<pii> st;
for(int i = 0; i < (int)row.size(); i++) {
while(!st.empty() && st.top().F <= row[i]) {
P[i].PB(st.top().S);
st.pop();
}
if(!st.empty()) P[i].PB(st.top().S);
st.push({row[i], i});
}
return P;
}
struct BIT {
static const int mxn = 2505;
int val[mxn];
// 0-based input
void add(int i, int x) {
i++;
while(i < mxn) {
val[i] += x;
i += i&(-i);
}
}
int get(int i) {
i++;
int sum = 0;
while(i) {
sum += val[i];
i -= i&(-i);
}
return sum;
}
};
void test() {
auto result = good_pairs(vector<int>{4, 5, 2, 1, 3, 4});
auto expected = vector<vector<int>>{
vector<int>{},
vector<int>{0},
vector<int>{1},
vector<int>{2},
vector<int>{3, 2, 1},
vector<int>{4, 1},
};
assert(result == expected);
}
ll count_rectangles(vector<vector<int>> A) {
test();
int n = A.size(), m = A[0].size();
vector<vector<vector<int>>> rows(n), cols(m);
vector<vector<vector<int>>> rows_len(n), cols_len(m);
for(int i = 0; i < n; i++) {
rows[i] = good_pairs(A[i]);
rows_len[i] = vector<vector<int>>(m);
for(int j = 0; j < m; j++) {
rows_len[i][j] = vector<int>(rows[i][j].size(), 1);
if(i) {
for(int k = 0; k < rows[i][j].size(); k++) {
auto it = lower_bound(rows[i-1][j].begin(), rows[i-1][j].end(), rows[i][j][k], greater<int>());
if(it != rows[i-1][j].end() && *it == rows[i][j][k]) {
rows_len[i][j][k] += rows_len[i-1][j][distance(rows[i-1][j].begin(), it)];
}
}
}
}
}
for(int i = 0; i < m; i++) {
vector<int> col;
for(int j = 0; j < n; j++) col.PB(A[j][i]);
cols[i] = good_pairs(col);
cols_len[i] = vector<vector<int>>(n);
for(int j = 0; j < n; j++) {
cols_len[i][j] = vector<int>(cols[i][j].size(), 1);
if(i) {
for(int k = 0; k < cols[i][j].size(); k++) {
auto it = lower_bound(cols[i-1][j].begin(), cols[i-1][j].end(), cols[i][j][k], greater<int>());
if(it != cols[i-1][j].end() && *it == cols[i][j][k]) {
cols_len[i][j][k] += cols_len[i-1][j][distance(cols[i-1][j].begin(), it)];
}
}
}
}
}
ll ans = 0;
for(int i = 1; i < n; i++) {
BIT bit;
// look at rows (i-1, j) and cols of (i, j-1)
for(int j = 1; j < m; j++) {
assert(bit.get(m) == 0);
vector<pii> rows_sort_len;
for(int k = 1; k < rows[i-1][j].size(); k++) {
rows_sort_len.PB({rows_len[i-1][j][k], rows[i-1][j][k]});
}
sort(rows_sort_len.begin(), rows_sort_len.end());
int added = 0;
for(int k = cols[j-1][i].size()-1; k >= 0; k--) {
int a = cols[j-1][i][k];
while(!rows_sort_len.empty() && rows_sort_len.back().F >= i-a-1) {
bit.add(rows_sort_len.back().S, 1);
rows_sort_len.pop_back();
added++;
}
int b = cols_len[j-1][i][k];
if(i-a > 1) {
int cnt = added;
if(j-2-b >= 0) cnt -= bit.get(j-2-b);
ans += cnt;
}
}
for(int k = 1; k < rows[i-1][j].size(); k++) {
bit.add(rows[i-1][j][k], -1);
}
}
}
return ans;
}
