#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> find_borders(const vector<int> &a){
int n = (int) a.size();
stack<int> st;
vector<int> l(n), r(n);
for (int i = 0; i < n; i++){
while (!st.empty() && a[st.top()] < a[i]) st.pop();
l[i] = (st.empty() ? -1 : st.top());
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--){
while (!st.empty() && a[st.top()] < a[i]) st.pop();
r[i] = (st.empty() ? n : st.top());
st.push(i);
}
vector<pair<int, int>> ans;
set<pair<int, int>> s1; // (i, r[i])
set<pair<int, int>> s2; // (r[i], i)
for (int j = 0; j < n; j++){
while (!s2.empty()){
int i = s2.begin()->second;
if (r[i] < j){
s1.erase(make_pair(i, r[i]));
s2.erase(make_pair(r[i], i));
} else {
break;
}
}
assert(s1.size() == s2.size());
auto it = s1.end();
while (true){
if (it == s1.begin()) break;
it--;
int i = it->first;
if (i < l[j]) break;
if (i + 1 < j) ans.emplace_back(i + 1, j - 1);
}
s1.emplace(j, r[j]);
s2.emplace(r[j], j);
}
return ans;
}
const int MaxN = 2502;
vector<int> per_col[MaxN][MaxN];
vector<pair<int, int>> per_row[MaxN][MaxN];
int cnt[MaxN * MaxN];
vector<pair<int, int>> opening[MaxN];
vector<long long> vals_to_add[MaxN];
long long count_rectangles(vector<vector<int>> A) {
int n = (int) A.size(), m = (int) A[0].size();
for (int i = 1; i + 1 < n; i++){
vector<pair<int, int>> f = find_borders(A[i]);
for (auto [l, r] : f){
per_col[l][r].push_back(i);
}
}
for (int j = 1; j + 1 < m; j++){
vector<int> col(n);
for (int i = 0; i < n; i++) col[i] = A[i][j];
vector<pair<int, int>> f = find_borders(col);
for (auto [x, y] : f){
auto &v = per_row[x][y];
if (v.empty() || v.back().second != j - 1){
v.emplace_back(j, j);
} else {
v.back().second++;
}
}
}
for (int x = 0; x < n; x++){
for (int y = x; y < n; y++){
for (auto [l, r] : per_row[x][y]){
// cerr << x << ' ' << y << ' ' << l << ' ' << r << endl;
opening[l].emplace_back(r, x * n + y);
}
}
}
// cerr << endl;
long long ans = 0;
for (int l = 1; l < m - 1; l++){
for (auto [r, val] : opening[l]){
vals_to_add[r].push_back(val);
}
vector<long long> vals;
for (int r = m - 2; r >= l; r--){
for (long long val : vals_to_add[r]){
vals.push_back(val);
}
int sz = (int) per_col[l][r].size();
for (int ii = 0; ii < sz; ii++){
int x = per_col[l][r][ii];
if (ii > 0 && per_col[l][r][ii - 1] == x - 1) continue;
for (int jj = ii; jj < sz; jj++){
int y = per_col[l][r][jj];
if (y - x != jj - ii) break;
// cerr << l << ' ' << r << ' ' << x << ' ' << y << endl;
for (long long val : vals){
// cerr << val/n << ' ' << val%n << endl;
if (val / n >= x && val % n == y){
ans++;
}
}
// cerr << endl;
}
}
}
}
return ans;
}
