#include "rect.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
constexpr ll inf = (1ll<<60);
/*
constexpr ll LOG = 12;
ll left_table[2510][2510][LOG+1];
ll right_table[2510][2510][LOG+1];
ll up_table[2510][2510][LOG+1];
ll down_table[2510][2510][LOG+1];*/
struct binary_indexed_tree{
vi node;
ll N;
binary_indexed_tree(int n): N(n){
node.resize(N+1);
}
void add(ll idx, ll val){
idx++;
for(; idx<=N; idx+=(idx&-idx)) node[idx] += val;
}
ll sum(ll idx){
idx++;
ll ret = 0;
for(; 0<idx; idx-=(idx&-idx)) ret += node[idx];
return ret;
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
ll H = a.size(), W = a[0].size();
vii left(H,vi(W)), right(H,vi(W)), down(H,vi(W)), up(H,vi(W));
ll ans = 0;
{
rep(i,0,H){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(-1);
rep(j,0,W){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
left[i][j] = idx[0];
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
}
}
{
rep(i,0,H){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(W);
per(j,W-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
right[i][j] = idx[0];
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
}
}
{
rep(j,0,W){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(-1);
rep(i,0,H){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
up[i][j] = idx[0];
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
}
}
{
rep(j,0,W){
std::deque<ll> max, idx;
max.pb(inf);
idx.pb(H);
per(i,H-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
down[i][j] = idx[0];
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
}
}
rep(j,1,W-1){
vi up_state(H,-inf);
vi down_state(H,inf);
rep(k,j,W-1){
rep(i,0,H){
up_state[i] = std::max(up_state[i], up[i][k]);
down_state[i] = std::min(down_state[i], down[i][k]);
}
binary_indexed_tree bit(H);
vii mem(H+1);
ll last = 0;
rep(l,1,H-1){
mem[down_state[l-1]].pb(l);
for(auto el: mem[l]) bit.add(el, -1);
bit.add(l,1);
if(right[l][j-1] <= k || left[l][k+1] >= j){
last = l;
}
else{
ll b = std::max(last, up_state[l+1]);
ans += bit.sum(l)-bit.sum(b);
}
}
}
}
return ans;
}
