#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "rect.h"
#else
#include "grader.cpp"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 2505;
int n, m;
ll ans;
int a[SIZE][SIZE];
int U[SIZE][SIZE], D[SIZE][SIZE];
int L[SIZE][SIZE], R[SIZE][SIZE];
ll n_small() {
if (n < 3) return 0;
FOR (l, 2, m - 1) {
int mx = 0;
FOR (r, l, m - 1) {
if (a[2][r] >= min(a[1][r], a[3][r])) break;
mx = max(mx, a[2][r]);
ans += (mx < min(a[2][l - 1], a[2][r + 1]));
}
}
return ans;
}
int bit[SIZE];
void upd(int pos, int x) {
for (; pos <= m; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
int re = 0;
for (; pos; pos -= pos & -pos) re += bit[pos];
return re;
}
int que(int l, int r) {
return l > r ? 0 : que(r) - que(l - 1);
}
int curL[SIZE], curR[SIZE], cnt[SIZE];
ll count_rectangles(vector<vector<int>> _a) {
n = _a.size(), m = _a[0].size(), ans = 0;
FOR (i, 1, n) FOR (j, 1, m) a[i][j] = _a[i - 1][j - 1];
if (n <= 3) return n_small();
FOR (i, 1, n) {
vector<int> st;
FOR (j, 1, m) {
while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
L[i][j] = (st.size() ? st.back() + 1 : 1);
st.pb(j);
}
st.clear();
for (int j = m; j >= 1; j--) {
while (st.size() && a[i][j] > a[i][st.back()]) st.pop_back();
R[i][j] = (st.size() ? st.back() - 1 : m);
st.pb(j);
}
}
FOR (j, 1, m) {
vector<int> st;
FOR (i, 1, n) {
while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
U[i][j] = (st.size() ? st.back() + 1 : 1);
st.pb(i);
}
st.clear();
for (int i = n; i >= 1; i--) {
while (st.size() && a[i][j] > a[st.back()][j]) st.pop_back();
D[i][j] = (st.size() ? st.back() - 1 : n);
st.pb(i);
}
}
FOR (u, 2, n - 1) {
fill(curL + 1, curL + m + 1, 0);
fill(curR + 1, curR + m + 1, m + 1);
FOR (d, u, n - 1) {
FOR (j, 1, m) {
curL[j] = max(curL[j], L[d][j]);
curR[j] = min(curR[j], R[d][j]);
}
auto cal = [&](int l, int r) {
vector<pair<int, int>> all;
FOR (j, l, r) all.pb(max(l, curL[j + 1]), j);
sort(all.begin(), all.end());
int p = 0;
FOR (j, l, r) {
while (p < all.size() && all[p].F <= j) upd(all[p].S, 1), p++;
ans += que(j, curR[j - 1]);
}
while (p > 0) {
p--;
upd(all[p].S, -1);
}
};
int l = 0;
FOR (j, 2, m - 1) if (D[u - 1][j] >= d && U[d + 1][j] <= u) {
if (l == 0) l = j;
if (j == m - 1 || !(D[u - 1][j + 1] >= d && U[d + 1][j + 1] <= u)) {
int r = j;
cal(l, r);
l = 0;
}
}
}
}
return ans;
}
/*
in1
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
out1
6
*/
