#include<bits/stdc++.h>
using namespace std;
const int N = 2500 + 5;
const int MX = 7e6 + 5;
struct SegTree {
vector<int> st;
SegTree(int n) {
st.assign(4 * n, 0);
}
void update(int v, int tl, int tr, int idx, int add) {
if (tl == tr) {
st[v] += add;
return;
}
int mid = tl + (tr - tl) / 2;
if (idx <= mid) update(2 * v, tl, mid, idx, add);
else update(2 * v + 1, mid + 1, tr, idx, add);
st[v] = st[2 * v] + st[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) return st[v];
int mid = tl + (tr - tl) / 2;
return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
}
};
vector<pair<int,int>> sorted[MX];
set<int> col[N];
vector<int> row_order[N];
vector<int> col_has[N][N];
bool has[N][N];
long long int count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) sorted[a[i][j]].push_back({i, j});
}
for (int i = 0; i < N; i++) {
col[i].insert(-1);
col[i].insert(n);
}
for (int i = MX - 1; i >= 0; i--) {
for (auto [x, y]: sorted[i]) {
row_order[x].push_back(y);
col[y].insert(x);
}
for (auto [x, y]: sorted[i]) {
auto it = col[y].find(x);
it--;
if (*it != -1 && *it < x - 1) {
int l = (*it) + 1;
int r = x - 1;
col_has[l][y].push_back(r);
}
it++;
it++;
if (*it != n && *it > x + 1) {
int l = x + 1;
int r = (*it) - 1;
col_has[l][y].push_back(r);
}
}
}
long long int ans = 0;
SegTree st(m);
for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) has[i][j] = false;
vector<pair<int,int>> dp_row[N];
for (int i = n - 2; i > 0; i--) {
set<int> row;
row.insert(-1);
row.insert(m);
vector<int> row_has[N];
int p = 0;
while (p < m) {
int curr = a[i][row_order[i][p]];
int start = p;
while (p < m && a[i][row_order[i][p]] == curr) {
row.insert(row_order[i][p++]);
}
for (int j = start; j < p; j++) {
int y = row_order[i][j];
auto it = row.find(y);
it--;
if (*it != -1 && *it < y - 1) {
int l = (*it) + 1;
int r = y - 1;
row_has[l].push_back(r);
has[l][r] = true;
}
it++;
it++;
if (*it != m && *it > y + 1) {
int l = y + 1;
int r = (*it) - 1;
row_has[l].push_back(r);
has[l][r] = true;
}
}
}
vector<pair<int,int>> dp_col;
for (int j = m - 2; j > 0; j--) {
vector<pair<int,int>> ndp_col;
int p1 = 0, p2 = 0;
while (p1 < col_has[i][j].size() || p2 < dp_col.size()) {
if (p1 == col_has[i][j].size()) p2++;
else if (p2 == dp_col.size()) ndp_col.emplace_back(col_has[i][j][p1++], j);
else if (col_has[i][j][p1] > dp_col[p2].first) ndp_col.emplace_back(col_has[i][j][p1++], j);
else if (col_has[i][j][p1] < dp_col[p2].first) p2++;
else {
p1++;
ndp_col.push_back(dp_col[p2++]);
}
}
dp_col = move(ndp_col);
vector<pair<int,int>> ndp_row;
for (auto [x, y]: dp_row[j]) {
if (!has[j][y]) continue;
has[j][y] = false;
assert(ndp_row.empty() || ndp_row.back().first >= x);
ndp_row.emplace_back(x, y);
}
for (auto x: row_has[j]) {
if (!has[j][x]) continue;
has[j][x] = false;
assert(ndp_row.empty() || ndp_row.back().first >= i);
ndp_row.emplace_back(i, x);
}
dp_row[j] = move(ndp_row);
int ptr = 0;
for (auto [x, y]: dp_col) {
while (ptr < dp_row[j].size() && dp_row[j][ptr].first >= x) {
st.update(1, 0, m - 1, dp_row[j][ptr++].second, 1);
}
ans += st.query(1, 0, m - 1, j, y);
}
while (--ptr >= 0) {
st.update(1, 0, m - 1, dp_row[j][ptr].second, -1);
}
}
}
return ans;
}
