#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], u[N][N], d[N][N], l[N][N], r[N][N];
void prec() {
for(int i = 1; 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();
}
l[i][j] = (st.empty() ? 0 : st.back());
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();
}
r[i][j] = (st.empty() ? m + 1 : st.back());
st.push_back(j);
}
}
for(int j = 1; 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();
}
u[i][j] = (st.empty() ? 0 : st.back());
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();
}
d[i][j] = (st.empty() ? n + 1 : st.back());
st.push_back(i);
}
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= m; j++) {
// cout << d[i][j] << ' ';
// }
// cout << '\n';
// }
}
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();
ll res = 0;
for(int i = 2; i < n; i++) {
vector<int> x(m + 1, m + 1), y(m + 1, 0);
for(int j = i; j < n; j++) {
for(int k = 2; k < m; k++) {
x[k] = min(x[k], r[j][k - 1]);
y[k] = max(y[k], l[j][k + 1]);
}
for(int k = 2; k < m; k++) {
for(int f = k; f < m; f++) {
if(d[i - 1][f] <= j || u[j + 1][f] >= i) {
break;
}
// cout << i << ' ' << j << ' ' << k << ' ' << f << ' ' << x[k] << ' ' << y[f] << '\n';
if(x[k] > f && y[f] < k) {
res++;
}
}
}
}
}
return res;
}
