#include "rect.h"
#include "bits/stdc++.h"
#define pb push_back
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
struct event {
int time, val, type;
};
bool cmp(event a, event b) {
if(a.time > b.time) return 1;
if(a.time < b.time) return 0;
return a.type < b.type;
}
const int N = 3000;
ll fen[N];
void modif(int u, int val) {
for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
ll query(int u) {
ll ret = 0;
for(int i = u + 1; i > 0; i -= i & -i) ret += fen[i];
return ret;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<pair<int, int>> right[n + 1][m + 1], down[n + 1][m + 1];
for(int i = 0; i < n; ++i) {
stack<int> s;
for(int j = m - 1; j >= 0; --j) {
while(!s.empty() && a[i][j] > a[i][s.top()]) {
if(j + 1 <= s.top() - 1) {
right[i][j + 1].pb(make_pair(s.top() - 1 - j, 1));
}
s.pop();
}
if(!s.empty()) {
if(j + 1 <= s.top() - 1) {
right[i][j + 1].pb(make_pair(s.top() - 1 - j, 1));
}
if(a[i][s.top()] == a[i][j]) s.pop();
}
s.push(j);
}
}
for(int i = 0; i < m; ++i) {
stack<int> s;
for(int j = n - 1; j >= 0; --j) {
while(!s.empty() && a[j][i] > a[s.top()][i]) {
if(j + 1 <= s.top() - 1) {
down[j + 1][i].pb(make_pair(s.top() - 1 - j, 1));
}
s.pop();
}
if(!s.empty()) {
if(j + 1 <= s.top() - 1) {
down[j + 1][i].pb(make_pair(s.top() - 1 - j, 1));
}
if(a[s.top()][i] == a[j][i]) s.pop();
}
s.push(j);
}
}
for(int i = n - 1; i >= 0; --i) {
for(int j = m - 1; j >=0; --j) {
for(auto& p: right[i][j]) {
auto it = lower_bound(all(right[i + 1][j]), p);
if(it != right[i + 1][j].end() && it->first == p.first) {
p.second = it->second + 1;
}
}
for(auto& p: down[i][j]) {
auto it = lower_bound(all(down[i][j + 1]), p);
if(it != down[i][j + 1].end() && it->first == p.first) {
p.second = it->second + 1;
}
}
}
}
ll ans = 0;
for(int i = 1; i < n - 1; ++i) {
for(int j = 1; j < m - 1; ++j) {
vector<event> v;
for(auto& p: down[i][j]) {
v.pb({p.second, p.first, 1});
}
for(auto& p: right[i][j]) {
v.pb({p.first, p.second, 2});
}
sort(all(v), cmp);
for(auto x: v) {
if(x.type == 1) {
modif(x.val, 1);
} else {
ans += query(x.val);
}
}
for(auto x: v) if(x.type == 1) modif(x.val, -1);
}
}
return ans;
}
