#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define _ <<' '<<
//void* MEM = malloc(400 << 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 {
//#include <ext/pb_ds/assoc_container.hpp>
//typedef __gnu_pbds::cc_hash_table<int, int> ht;
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];
unordered_map<int, int> fl[N];
vector<bool> mk;
int c[5 * N], cn, xn, yn;
pii x[N], y[N];
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(unordered_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;
unordered_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();
const auto &a = fl[j], &b = fu;
if(a.size() * b.size() < 5) {
for(const auto &i : a)
for(const auto &j : b)
ans += i.ft <= j.sd && j.ft <= i.sd;
continue;
}
cn = 0;
for(const auto &i : a) {
c[cn++] = i.ft;
c[cn++] = i.sd;
}
for(const auto &i : b) {
c[cn++] = i.ft;
c[cn++] = i.sd;
}
sort(c, c + cn);
cn = unique(c, c + cn) - c;
xn = yn = 0;
finit(cn);
auto find = [&] (const int &z) {return lower_bound(c, c + cn, z) - c;};
for(const auto &i : a) x[xn++] = {find(i.sd), find(i.ft)};
for(const auto &i : b) y[yn++] = {find(i.ft), find(i.sd)};
sort(x, x + xn);
sort(y, y + yn);
int it = 0;
for(int i = 0; i < xn; ++i) {
for(; it < yn && y[it].ft <= x[i].ft; ++it)
fadd(y[it].sd);
ans += fget(x[i].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 _
