#include "rect.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = int;
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
#define ln "\n"
constexpr ll inf = (1ll<<30);
/*
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();
long long ans = 0;
vector<vector<vector<pii>>> query(H,vector<vector<pii>>(W));
{
vector<std::map<ll,ll>> dp_right(W);
vector<std::map<ll,ll>> right(W);
per(i,H-1,0){
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();
}
if(idx[0] != -1) right[idx[0]][j] = 1;
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
max.clear();
idx.clear();
max.pb(inf);
idx.pb(W);
per(j,W-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != W) right[j][idx[0]] = 1;
max.emplace_front(a[i][j]);
idx.emplace_front(j);
}
rep(j,0,W){
if(right[j].count(j+1)) right[j].erase(j+1);
for(auto &el: right[j]){
if(dp_right[j].count(el.first)) el.second += dp_right[j][el.first];
}
}
rep(j,1,W-1){
for(auto el: right[j-1]){
ll bottom = i+el.second;
// bottom 以下 かつ
ll lasting = el.first-j;
// lasting 以上
query[i][j].pb(mp(lasting, -bottom));
}
}
rep(j,0,W){
dp_right[j] = right[j];
right[j].clear();
}
}
}
{
vector<std::map<ll,ll>> dp_down(H);
vector<std::map<ll,ll>> down(H);
per(j,W-1,0){
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();
}
if(idx[0] != -1) down[idx[0]][i] = 1;
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
max.clear();
idx.clear();
max.pb(inf);
idx.pb(H);
per(i,H-1,0){
while(max[0] < a[i][j]){
max.pop_front();
idx.pop_front();
}
if(idx[0] != H) down[i][idx[0]] = 1;
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
rep(i,0,H){
if(down[i].count(i+1)) down[i].erase(i+1);
for(auto &el: down[i]){
if(dp_down[i].count(el.first)) el.second += dp_down[i][el.first];
}
}
rep(i,1,H-1){
for(auto el: down[i-1]){
query[i][j].pb(mp(el.second, el.first));
}
}
rep(i,0,H){
dp_down[i] = down[i];
down[i].clear();
}
}
}
binary_indexed_tree bit(H+10);
rep(i,1,H-1){
rep(j,1,W-1){
auto query_ = query[i][j];
sort(all(query_));
reverse(all(query_));
for(auto el: query_){
if(el.second < 0) ans += bit.sum(-el.second);
else bit.add(el.second,1);
}
for(auto el: query_){
if(el.second > 0) bit.add(el.second,-1);
}
}
}
return ans;
}
