// In the name of Allah
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2500 + 4;
const int maxs = maxn * maxn * 2;
const int oo = 1e9 + 4;
int n, m; int L[maxn], R[maxn];
int A[maxn][maxn], Ax[maxn][maxn];
vector<pair<int, pii>> ls1, ls2;
int val1[maxs], val2[maxs];
vector<pii> lsx; int t[maxn];
int G1(pair<int, pii> x) {
int j = lower_bound(all(ls1), x) - ls1.begin();
if (j < len(ls1) && ls1[j] == x) return j;
return -1;
}
int G2(pair<int, pii> x) {
int j = lower_bound(all(ls2), x) - ls2.begin();
if (j < len(ls2) && ls2[j] == x) return j;
return -1;
}
void addx(int i, int x) {
for (++i; i < maxn; i += (i & -i)) t[i] += x;
}
int getx(int i) {
int res = 0;
for (++i; i > 0; i -= (i & -i)) res += t[i];
return res;
}
ll count_rectangles(vector<vector<int>> a) {
n = len(a); m = len(a[0]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
A[i][j] = a[i][j]; Ax[j][i] = A[i][j];
}
}
if (n < 3 || m < 3) return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (L[j] = j - 1; L[j] != -1 && A[i][j] > A[i][L[j]]; L[j] = L[L[j]]);
if (L[j] != -1 && (j - L[j]) >= 2) ls1.pb(Mp(i, Mp(L[j], j)));
}
for (int j = m - 1; j >= 0; j--) {
for (R[j] = j + 1; R[j] != m && A[i][j] > A[i][R[j]]; R[j] = R[R[j]]);
if (R[j] != m && (R[j] - j) >= 2 && A[i][j] != A[i][R[j]]) ls1.pb(Mp(i, Mp(j, R[j])));
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
for (L[i] = i - 1; L[i] != -1 && Ax[j][i] > Ax[j][L[i]]; L[i] = L[L[i]]);
if (L[i] != -1 && (i - L[i]) >= 2) ls2.pb(Mp(j, Mp(L[i], i)));
}
for (int i = n - 1; i >= 0; i--) {
for (R[i] = i + 1; R[i] != n && Ax[j][i] > Ax[j][R[i]]; R[i] = R[R[i]]);
if (R[i] != n && (R[i] - i) >= 2 && Ax[j][i] != Ax[j][R[i]]) ls2.pb(Mp(j, Mp(i, R[i])));
}
}
sort(all(ls1)); sort(all(ls2));
for (int i = len(ls1) - 1; i >= 0; i--) {
auto f = ls1[i]; int x = G1(Mp(f.F + 1, f.S));
if (x != -1) val1[i] = val1[x];
else val1[i] = f.F;
}
for (int i = len(ls2) - 1; i >= 0; i--) {
auto f = ls2[i]; int x = G2(Mp(f.F + 1, f.S));
if (x != -1) val2[i] = val2[x];
else val2[i] = f.F;
}
ll ans = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
int R1, R2;
lsx.clear();
R2 = lower_bound(all(ls2), Mp(j, Mp(i - 1, -1))) - ls2.begin();
for (; R2 < len(ls2) && ls2[R2].F == j && ls2[R2].S.F == i - 1; R2++) {
lsx.pb(Mp(val2[R2], ls2[R2].S.S - 1));
}
sort(all(lsx));
R2 = len(lsx) - 1;
R1 = lower_bound(all(ls1), Mp(i, Mp(j - 1, oo))) - ls1.begin() - 1;
for (; R1 >= 0 && ls1[R1].F == i && ls1[R1].S.F == j - 1; R1--) {
while (R2 >= 0 && lsx[R2].F >= ls1[R1].S.S - 1) {
addx(lsx[R2].S, 1); R2--;
}
ans += getx(val1[R1]);
}
while (R2 + 1 < len(lsx)) {
addx(lsx[R2 + 1].S, -1); R2++;
}
}
}
return ans;
}
