#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define _ <<' '<<
void* MEM = malloc(200 << 20);
void* operator new(const size_t f) {
void* res = MEM;
MEM += f;
return res;
}
void operator delete(void*) {}
//#pragma GCC optimize("Ofast,O3")
namespace S {
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vv;
typedef pair<int, int> pii;
const int N = 2505;
int n, m;
list<int> l[N][N], u[N][N];
int p[N], length[N], la[N];
map<int, int> fl[N];
vector<bool> mk;
int f[N * 5], fmax;
void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); }
void fadd(int i) { for(i = fmax - i; i <= fmax; i += i & -i) f[i]++; }
int fget(int i) { int v{}; for(i = fmax - i; i; i -= i & -i) v += f[i]; return v; }
int get(map<int, int> &a, int b) {
const auto f = a.find(b);
if(f == a.end()) return 0;
return f->sd;
}
ll solve() {
ll ans = 0;
map<int, int> cl, fu, cu;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
swap(cl, fl[j]);
for(const int &t : l[i][j])
fl[j][t] = get(cl, t) + 1;
cl.clear();
swap(cu, fu);
for(const int &t : u[i][j])
fu[t] = get(cu, t) + 1;
cu.clear();
vi c;
const auto &A = fl[j], &B = fu;
if(A.size() * B.size() < 20) {
for(const auto &i : A) {
for(const auto &j : B) {
if(i.ft <= j.sd && j.ft <= i.sd)
++ans;
}
}
continue;
}
c.reserve(A.size() + B.size() << 1);
for(const auto &i : A) {
c.push_back(i.ft);
c.push_back(i.sd);
}
for(const auto &i : B) {
c.push_back(i.ft);
c.push_back(i.sd);
}
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
finit(c.size());
list<pii> a, b;
auto find = [&] (const int &z) {return lower_bound(c.begin(), c.end(), z) - c.begin();};
for(const auto &i : A) a.push_back({find(i.sd), find(i.ft)});
for(const auto &i : B) b.push_back({find(i.ft), find(i.sd)});
a.sort();
auto it = b.begin();
for(const auto t : a) {
for(; it != b.end() && it->ft <= t.ft; ++it)
fadd(it->sd);
ans += fget(t.sd);
}
}
fu.clear();
}
return ans;
}
int last(int i) {
return la[i] == i ? i : la[i] = last(la[i]);
}
void unite(int i, int j) {
i = last(i), j = last(j);
length[j] += length[i];
la[i] = j;
}
}
S::ll count_rectangles(S::vv a) {
using namespace S;
n = a.size();
m = a[0].size();
for(int i = 0; i < n; ++i) {
iota(p, p + m, 0);
iota(la, la + m, 0);
mk.assign(m, false);
sort(p, p + m, [&] (const int &fi, const int &se) {return a[i][fi] < a[i][se];});
for(int t = 0; t < m; ) {
int v = a[i][p[t]];
list<int> f;
for(; t < m && a[i][p[t]] == v; ++t) {
int j = p[t];
mk[j] = true;
length[j] = 1;
f.push_back(j);
if(j + 1 < m && mk[j + 1]) unite(j, j + 1);
if(j && mk[j - 1]) unite(j - 1, j);
}
for(int i : f) mk[last(i)] = false;
for(int j : f) {
j = last(j);
if(mk[j]) continue;
mk[j] = true;
if(i == 0 || i == n - 1) continue;
if(j == m - 1 || length[j] == j + 1) continue;
l[i][j].push_back(length[j]);
}
}
}
for(int j = 0; j < m; ++j) {
iota(p, p + n, 0);
iota(la, la + n, 0);
mk.assign(n, false);
sort(p, p + n, [&] (const int &fi, const int &se) {return a[fi][j] < a[se][j];});
for(int t = 0; t < n; ) {
int v = a[p[t]][j];
list<int> f;
for(; t < n && a[p[t]][j] == v; ++t) {
int i = p[t];
mk[i] = true;
length[i] = 1;
f.push_back(i);
if(i + 1 < n && mk[i + 1]) unite(i, i + 1);
if(i && mk[i - 1]) unite(i - 1, i);
}
for(int j : f) mk[last(j)] = false;
for(int i : f) {
i = last(i);
if(mk[i]) continue;
mk[i] = true;
if(j == 0 || j == m - 1) continue;
if(i == n - 1 || length[i] == i + 1) continue;
u[i][j].push_back(length[i]);
}
}
}
return solve();
}
#undef ft
#undef sd
#undef _
