#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 2505;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
vector<int> vxi[MAXN][MAXN];
vector<pi> vx[MAXN][MAXN];
vector<pi>vy1[MAXN];
vector<pi> vy[MAXN][MAXN];
unordered_set<int> us[MAXN][MAXN];
struct hash_pair {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pair<uint64_t,uint64_t> x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
}
};
int n,m;
long long ans;
struct fenw {
int fw[MAXN];
void update(int x, int nval){
for(;x<MAXN;x+=x&-x)fw[x]+=nval;
}
int point(int x){
int res=0;
for(;x;x-=x&-x)res+=fw[x];
return res;
}
int query(int x, int y){
return point(y)-point(x-1);
}
}fw;
long long count_rectangles(std::vector<std::vector<int> > A) {
n=A.size();
m=A[0].size();
for(int i=1;i<=n;i++){
vector<pi> E;
for(int j=1;j<=m;j++){
E.push_back({A[i-1][j-1],j});
}
sort(E.begin(),E.end(),greater<pi>());
set<int> s;
vector<int> lazy;
int pre=-1;
set<pi> st;
for(auto x:E){
if(x.first!=pre){
for(auto y:lazy){
s.insert(y);
}
lazy.clear();
}
//debug(x.first,x.second);
auto it=s.lower_bound(x.second);
if(it == s.begin() || it==s.end());
else {
int L=*prev(it);
int R=*it;
st.insert({L,R});
}
lazy.push_back(x.second);
pre=x.first;
}
for(auto x:st){
int L=x.first;
int R=x.second;
vy1[i].push_back({L,R});
us[L][R].insert(i);
}
}
for(int i=1;i<=n;i++){
vy1[i].resize(unique(vy1[i].begin(),vy1[i].end())-vy1[i].begin());
}
for(int i=1;i<=m;i++){
vector<pi> E;
for(int j=1;j<=n;j++){
E.push_back({A[j-1][i-1],j});
}
sort(E.begin(),E.end(),greater<pi>());
set<int> s;
vector<int> lazy;
int pre=-1;
set<pi> st;
for(auto x:E){
if(x.first!=pre){
for(auto y:lazy){
s.insert(y);
}
lazy.clear();
}
//debug(x.first,x.second);
auto it=s.lower_bound(x.second);
if(it == s.begin() || it==s.end());
else {
int L=*prev(it);
int R=*it;
//vxi[L][R].push_back(i);
st.insert({L,R});
}
lazy.push_back(x.second);
pre=x.first;
}
for(auto x:st){
vxi[x.first][x.second].push_back(i);
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int st=0;
for(int k=0;k<(int)vxi[i][j].size();k++){
if(k==((int)vxi[i][j].size()-1) || vxi[i][j][k]+1!=vxi[i][j][k+1]){
vx[i][j].push_back({vxi[i][j][st],vxi[i][j][k]});
st=k+1;
}
}
}
}
for(int i=1;i<=n;i++){
unordered_set<pi,hash_pair> vy;
for(auto x:vy1[i+1]){
vy.insert(x);
}
for(int j=i+2;j<=n;j++){
//sort(vx[i][j].begin(),vx[i][j].end());
vector<array<int,3>> events;
for(auto x:vx[i][j]){
events.push_back({x.second,1,x.first});
}
for(auto x:vy){
events.push_back({x.second-1,-1,x.first+1});
}
sort(events.begin(),events.end());
vector<pi> reset;
for(auto e:events){
if(e[1] == -1){
fw.update(e[2],1);
reset.push_back({e[2],-1});
} else{
ans+=fw.query(e[2],e[0]);
}
}
for(auto x:reset)fw.update(x.first,x.second);
vector<pi> toerase;
for(auto x:vy){
if(us[x.first][x.second].find(j) == us[x.first][x.second].end())toerase.push_back(x);
}
for(auto x:toerase){
vy.erase(x);
}
}
}
return ans;
}
