#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2500 + 12;
int n, m, a[N][N], it[N][N];
vector<array<int, 2>> r[N];
vector<int> id[N][N], t[N][N], f[N][N];
void prec() {
for(int i = 2; i < n; i++) {
vector<int> st;
for(int j = 1; j <= m; j++) {
while(!st.empty() && a[i][st.back()] < a[i][j]) {
st.pop_back();
}
if(!st.empty()) {
int l = st.back();
if(l + 1 <= j - 1) {
r[i].push_back({l + 1, j - 1});
}
}
st.push_back(j);
}
st.clear();
for(int j = m; j >= 1; j--) {
while(!st.empty() && a[i][st.back()] < a[i][j]) {
st.pop_back();
}
if(!st.empty()) {
int l = st.back();
if(j + 1 <= l - 1) {
r[i].push_back({j + 1, l - 1});
}
}
st.push_back(j);
}
sort(r[i].begin(), r[i].end());
r[i].resize(unique(r[i].begin(), r[i].end()) - r[i].begin());
for(auto [l, r]:r[i]) {
id[l][r].push_back(i);
}
}
for(int j = 2; j < m; j++) {
vector<int> st;
for(int i = 1; i <= n; i++) {
while(!st.empty() && a[st.back()][j] < a[i][j]) {
st.pop_back();
}
if(!st.empty()) {
int l = st.back();
if(l + 1 <= i - 1) {
t[l + 1][j].push_back(i - 1);
}
}
st.push_back(i);
}
st.clear();
for(int i = n; i >= 1; i--) {
while(!st.empty() && a[st.back()][j] < a[i][j]) {
st.pop_back();
}
if(!st.empty()) {
int l = st.back();
if(l - 1 >= i + 1) {
t[i + 1][j].push_back(l - 1);
}
}
st.push_back(i);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sort(t[i][j].begin(), t[i][j].end());
t[i][j].resize(unique(t[i][j].begin(), t[i][j].end()) - t[i][j].begin());
}
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
f[i][j].resize((int)id[i][j].size());
for(int k = 0; k < (int)f[i][j].size(); k++) {
if(k && id[i][j][k] - 1 == id[i][j][k - 1]) {
f[i][j][k] = f[i][j][k - 1];
} else {
int it = k + 1;
while(it < (int)id[i][j].size() && id[i][j][it] - 1 == id[i][j][it - 1]) {
it++;
}
it--;
f[i][j][k] = id[i][j][it];
}
}
}
}
}
ll solve() {
ll res = 0;
for(int i = 2; i < n; i++) {
vector<array<int, 2>> pt;
for(int j = 2; j < m; j++) {
for(int f:t[i][j]) {
pt.push_back({f, j});
}
}
sort(pt.begin(), pt.end());
vector<array<int, 3>> s;
for(int i = 0; i < (int)pt.size(); ) {
int j = i + 1;
while(j < (int)pt.size() && pt[j][0] == pt[j - 1][0] && pt[j][1] == pt[j - 1][1] + 1) {
j++;
}
s.push_back({pt[i][0], pt[i][1], pt[j - 1][1]});
i = j;
}
for(auto [l, r]:r[i]) {
for(auto [g, L, R]:s) {
if(L <= l && R >= r && g <= f[l][r][it[l][r]]) {
res++;
}
}
}
for(auto [l, r]:r[i]) {
it[l][r]++;
}
}
return res;
}
ll count_rectangles(vector<vector<int> > _A) {
n = (int)_A.size();
m = (int)_A[0].size();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] = _A[i - 1][j - 1];
}
}
prec();
return solve();
}
