// na mn tanha nistam :) hich vaghtam bi bahre naboodam ...
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int lg = 12;
const int maxn5 = 2510;
int n, m;
vector <int> av;
ll ans = 0;
int lef[maxn5][maxn5], rig[maxn5][maxn5];
int dw[maxn5][maxn5], up[maxn5][maxn5];
pair <int, int> have[2][maxn5][maxn5], ex[2][maxn5][maxn5];
namespace rmqmn{
int mn[lg][maxn5];
void build(int n){
for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
mn[i][j] = min(mn[i - 1][j], (j + (1 << (i - 1)) < n ? mn[i - 1][j + (1 << (i - 1))] : maxn5));
}
int get(int l, int r){
if(r < l)
return 0;
int k = 31 - __builtin_clz(r - l + 1);
return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
}
namespace rmqmx{
int mx[lg][maxn5];
void build(int n){
for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1)) < n ? mx[i - 1][j + (1 << (i - 1))] : maxn5));
}
int get(int l, int r){
if(r < l)
return 0;
int k = 31 - __builtin_clz(r - l + 1);
return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
}
namespace fen{
int fen[maxn5];
ll all = 0;
void add(int id, int val){
all += val;
for(id += 5; id < maxn5; id += id & -id)
fen[id] += val;
}
int get(int id){
int ret = 0;
for(id += 4; id; id -= id & -id)
ret += fen[id];
return all - ret;
}
}
namespace anscalcer{
vector <pair<int, int>> req[2], rem;
void clear(){
req[0].clear();
req[1].clear();
rem.clear();
}
void add(int ty, int l, int r){
////cout << "here " << ty << ' ' << l << ' ' << r << endl;
if(ty){
req[ty].pb({l, r});
rem.pb({r, l});
}
else{
req[ty].pb({r, l});
}
}
void calc(){
sort(all(req[0]));
sort(all(req[1]));
sort(all(rem));
int ind = 0, ind2 = 0;
for(auto [r, l] : req[0]){
while(ind < req[1].size() && req[1][ind].fi + 2 <= r){
fen::add(req[1][ind].fi, 1);
ind++;
}
while(ind2 < rem.size() && rem[ind2].fi < l){
fen::add(rem[ind2].se, -1);
ind2++;
}
ans += fen::get(l);
}
while(ind2 < rem.size()){
fen::add(rem[ind].se, -1);
ind2++;
}
}
}
bool exi(int id, int l, int r){
return id >= 0 && id < n && (lef[id][r] == l || rig[id][l] == r);
}
pair <int, int> get_val(int id, int l, int r){
// << id << ' ' << l << ' ' << r << endl;
if(lef[id][r] == l)
return have[0][id][r];
if(rig[id][l] == r)
return have[1][id][l];
if(id && rig[id - 1][l] == r)
return ex[1][id - 1][l];
if(id && lef[id - 1][r] == l)
return ex[0][id - 1][r];
if(id + 1 < n && rig[id + 1][l] == r)
return ex[1][id + 1][l];
if(id + 1 < n && lef[id + 1][r] == l)
return ex[0][id + 1][r];
}
void solve(int id, int l, int r){
//cout << "ha? " << id << ' ' << l << ' ' << r << endl;
if(id > 1 && exi(id - 1, l, r))
return;
int rq = id + 1;
while(rq < n - 1 && exi(rq, l, r))
rq++;
anscalcer::clear();
//cout << "solve of " << id << ' ' << rq << ' ' << l << ' ' << r << endl;
for(int i = max(0, id - 1); i <= rq; i++){
pair <int, int> ret = get_val(i, l, r);
////cout << i << ' ' << ret.fi << ' ' << ret.se << endl;
if(ret.fi + 1 < i && i >= id)
anscalcer::add(0, ret.fi, i);
if(i + 1 < ret.se && i < rq)
anscalcer::add(1, i, ret.se);
}
anscalcer::calc();
//cout << "finally " << ans << endl;
return;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
memset(up, -1, sizeof up);
if(min(n, m) < 3)
return 0;
for(int j = 0; j < m; j++){
av.clear();
for(int i = 0; i < n; i++){
while(av.size() && a[av.back()][j] < a[i][j]){
dw[av.back()][j] = i;
av.pop_back();
}
dw[i][j] = n;
if(av.size()){
if(a[av.back()][j] == a[i][j]){
up[i][j] = av.back();
dw[av.back()][j] = i;
av.pop_back();
}
else
up[i][j] = av.back();
}
av.pb(i);
}
}
memset(lef, -1, sizeof lef);
for(int i = 0; i < n; i++){
av.clear();
for(int j = 0; j < m; j++){
rig[i][j] = m;
while(av.size() && a[i][av.back()] < a[i][j]){
rig[i][av.back()] = j;
av.pop_back();
}
if(av.size()){
//cout << i << ' ' << j << ' ' << av.back() << ' ' << a[i][av.back()] << endl;
if(a[i][av.back()] == a[i][j]){
lef[i][j] = av.back();
rig[i][av.back()] = j;
av.pop_back();
}
else
lef[i][j] = av.back();
}
av.pb(j);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
rmqmx::mx[0][j] = up[i][j];
rmqmn::mn[0][j] = dw[i][j];
}
rmqmx::build(m);
rmqmn::build(m);
for(int j = 0; j < m; j++){
if(lef[i][j] != -1){
have[0][i][j].fi = rmqmx::get(lef[i][j] + 1, j - 1);
have[0][i][j].se = rmqmn::get(lef[i][j] + 1, j - 1);
if(i && !exi(i - 1, lef[i][j], j))
ex[0][i][j].se = rmqmn::get(lef[i][j] + 1, j - 1);
if(i + 1 < n && !exi(i + 1, lef[i][j], j))
ex[0][i][j].fi = rmqmx::get(lef[i][j] + 1, j - 1);
}
if(rig[i][j] != -1){
have[1][i][j].fi = rmqmx::get(j + 1, rig[i][j] - 1);
have[1][i][j].se = rmqmn::get(j + 1, rig[i][j] - 1);
if(i && !exi(i - 1, j, rig[i][j]))
ex[1][i][j].se = rmqmn::get(j + 1, rig[i][j] - 1);
if(i + 1 < n && !exi(i + 1, j, rig[i][j]))
ex[1][i][j].fi = rmqmx::get(j + 1, rig[i][j] - 1);
}
}
}
for(int i = 1; i < n - 1; i++) for(int j = 0; j < m; j++){
//cout << "*** " << i << ' ' << j << ' ' << lef[i][j] << ' ' << rig[i][j] << endl;
if(lef[i][j] != -1 && (j != rig[i][lef[i][j]]) && lef[i][j] + 1 < j){
////cout << "hmm " << rig[i][lef[i][j]] << endl;
solve(i, lef[i][j], j);
}
if(rig[i][j] < m && j + 1 < rig[i][j])
solve(i, j, rig[i][j]);
}
return ans;
}
