#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
const int MOD = 1000000007;
#define ins insert
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define all(x) begin(x), end(x)
const int mx = 2505;
int n, m;
set<int> ints1[mx][mx];
set<int> ints2[mx][mx];
vpi queries[mx][mx];
vpi updates[mx][mx];
vpi getInts(vi a){
// cout << "Q: ";
// for(auto u: a) cout << u << " ";
// cout << "\n";
vpi res;
set<pair<pi, pi>> rang; //l, r, leftval, rightval (outside range)
rang.ins(mp(mp(0, sz(a)-1), mp(MOD, MOD)));
vpi vals;
for(int i = 0; i < sz(a); i++){
vals.pb(mp(a[i], i));
}
sort(vals.rbegin(), vals.rend());
for(int i = 0; i < sz(vals); i++){
pair<pi, pi> b = *(prev(rang.lb(mp(mp(vals[i].s, MOD), mp(0, 0)))));
//cout << i << "\n";
assert(b.f.f <= vals[i].s && vals[i].s <= b.f.s);
rang.erase(b);
//if vals[i] is the max in range & if not on boundary
if(vals[i].f < max(b.s.f, b.s.s) && 1 <= b.f.f && b.f.s <= sz(a)-2){
res.pb(b.f);
}
//only divide if range added
if(b.f.f <= vals[i].s-1){
rang.ins(mp(mp(b.f.f, vals[i].s-1), mp(b.s.f, vals[i].f)));
}
if(vals[i].s+1 <= b.f.s){
rang.ins(mp(mp(vals[i].s+1, b.f.s), mp(vals[i].f, b.s.s)));
}
}
// cout << "R: ";
// for(auto u: res) cout << "(" << u.f << " " << u.s << "), ";
// cout << "\n";
return res;
}
int val[mx];
vi curin;
void upd(int a, int v){
if(v == 1) curin.pb(a);
for(; a < mx; a+=a&-a) val[a]+=v;
}
int sum(int a){
int res = 0;
for(; a > 0; a-=a&-a) res+=val[a];
return res;
}
int query(int a, int b){
return sum(b)-sum(a-1);
}
void clearBIT(){
for(auto u: curin){
upd(u, -1);
}
curin.clear();
}
ll count_rectangles(vector<vi> a){
n = sz(a);
m = sz(a[0]);
for(int i = 1; i+1 < n; i++){
vi nums;
for(int j = 0; j < m; j++){
nums.pb(a[i][j]);
}
vpi a = getInts(nums);
for(auto u: a){
ints1[i][u.f].ins(u.s);
}
}
for(int i = 1; i+1 < n; i++){
for(int j = 1; j+1 < m; j++){
set<int> vals = ints1[i][j];
for(auto u: vals){
for(int K = i; K+1 < n; K++){
if(!ints1[K+1][j].count(u)){
for(int k = i; k <= K; k++){
queries[k][j].pb(mp(K, u));
//cout << "Q: " << k << " " << j << " " << K << " " << u << "\n";
assert(ints1[k][j].count(u));
ints1[k][j].erase(u);
}
break;
}
}
}
}
}
for(int j = 1; j+1 < m; j++){
//cout << "j: " << j << "\n";
vi nums;
for(int i = 0; i < n; i++){
nums.pb(a[i][j]);
}
vpi a = getInts(nums);
// cout << "a: " << "\n";
// for(auto u: a){
// cout << u.f << " " << u.s << "\n";
// }
for(auto u: a){
ints2[u.f][j].ins(u.s);
}
}
for(int j = 1; j+1 < m; j++){
for(int i = 1; i+1 < n; i++){
set<int> vals = ints2[i][j];
for(auto u: vals){
for(int K = j; K+1 < m; K++){
if(!ints2[i][K+1].count(u)){
for(int k = j; k <= K; k++){
updates[i][k].pb(mp(u, K));
//cout << "U: " << i << " " << k << " " << u << " " << K << "\n";
//cout << i << " " << j << " " << k << "\n";
assert(ints2[i][k].count(u));
ints2[i][k].erase(u);
}
break;
}
}
}
}
}
ll ans = 0;
for(int i = 1; i+1 < n; i++){
for(int j = 1; j+1 < m; j++){
sort(all(queries[i][j]));
sort(all(updates[i][j]));
int updind = 0;
for(auto u: queries[i][j]){
while(updind < sz(updates[i][j])){
if(updates[i][j][updind].f <= u.f){
upd(updates[i][j][updind].s, 1);
updind++;
}
else break;
}
ans+=query(u.s, 2504); //number of things >=
}
clearBIT();
}
}
return ans;
}
