#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];
int c[N][N];
void upd(int x, int y, int val) {
c[x][y] += val;
// while(x <= m) {
// int j = y;
// while(j <= m) {
// c[x][j] += val;
// j += j & -j;
// }
// x += x & -x;
// }
}
int get(int x, int y) {
// for()
int ret = 0;
while(x) {
int j = y;
while(j) {
ret += c[x][j];
j -= j & -j;
}
x -= x & -x;
}
return ret;
}
int get(int x, int y, int x1, int y1) {
int ret = 0;
for(int i = x; i <= x1; i++) {
for(int j = y; j <= y1; j++) {
ret += c[i][j];
}
}
return ret;
return get(x1, y1) - get(x - 1, y1) - get(x1, y - 1) + get(x - 1, y - 1);
}
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 <= m; i++) {
for(int j = i; j <= m; 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++;
}
assert(pt[i][1] >= 1 && pt[j - 1][1] <= m);
s.push_back({pt[i][0], pt[i][1], pt[j - 1][1]});
i = j;
}
sort(s.begin(), s.end());
sort(r[i].begin(), r[i].end(), [&](array<int, 2> x, array<int, 2> y){
return f[x[0]][x[1]][it[x[0]][x[1]]] < f[y[0]][y[1]][it[y[0]][y[1]]];
});
int ti = 0;
for(auto [l, r]:r[i]) {
while(ti < (int)s.size() && s[ti][0] <= f[l][r][it[l][r]]) {
upd(s[ti][1], s[ti][2], 1);
ti++;
}
res += get(1, l, r, m);
// for(int j = 0; j < ti; j++) {
// if(s[j][1] <= l && s[j][2] >= r) {
// res++;
// }
// }
}
memset(c, 0, sizeof(c));
// for(int j = 0; j < ti; j++) {
// upd(s[j][1], s[j][2], -1);
// }
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();
}
