#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<utility>
using namespace std;
typedef long long ll;
long long count_rectangles(std::vector<std::vector<int> > a) {
ll ans = 0;
int n = (int)a.size();
int m = (int)a[0].size();
if(n <= 2 || m <= 2) return 0;
vector<vector<bitset<2505>>> visr(n, vector<bitset<2505>>(m)), visc(m, vector<bitset<2505>>(n));
vector<vector<pair<int, int>>> r(n), c(m);
for(int i = 1; i < n - 1; i++){
vector<pair<int, int>> st;
for(int j = 0; j < m; j++){
while(!st.empty() && st.back().first < a[i][j]){
auto x = st.back();
st.pop_back();
if(x.second + 1 < j){
visr[i][x.second][j] = 1;
r[i].emplace_back(x.second, j);
}
}
if(!st.empty()){
auto &x = st.back();
if(x.second + 1 < j){
visr[i][x.second][j] = 1;
r[i].emplace_back(x.second, j);
}
}
st.emplace_back(a[i][j], j);
}
}
for(int i = 1; i < m - 1; i++){
vector<pair<int, int>> st;
for(int j = 0; j < n; j++){
while(!st.empty() && st.back().first < a[j][i]){
auto x = st.back();
st.pop_back();
if(x.second + 1 < j){
visc[i][x.second][j] = 1;
c[i].emplace_back(x.second, j);
}
}
if(!st.empty()){
auto &x = st.back();
if(x.second + 1 < j){
visc[i][x.second][j] = 1;
c[i].emplace_back(x.second, j);
}
}
st.emplace_back(a[j][i], j);
}
}
for(int i = 1; i < n - 1; i++){
vector<pair<int, int>> imp = r[i];
for(int j = i; j < n - 1; j++){
vector<pair<int, int>> tmp;
while(!imp.empty()){
auto [a, b] = imp.back();
imp.pop_back();
if(visr[j][a][b]) tmp.emplace_back(a, b);
}
imp = tmp;
vector<int> pre(m);
for(int k = 1; k < m - 1; k++){
if(visc[k][i - 1][j + 1]) pre[k] = pre[k - 1] + 1;
else pre[k] = pre[k - 1];
//cout << pre[k] << " ";
}
for(auto &[a, b]: imp){
if(pre[b - 1] - pre[a] == b - a - 1) ans++;
}
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run rect.cpp grader.cpp
