#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<std::map<ll,ll>>> right(H,vector<std::map<ll,ll>>(W));
vector<vector<std::map<ll,ll>>> down(H,vector<std::map<ll,ll>>(W));
{
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();
}
if(idx[0] != -1) right[i][idx[0]][j] = 1;
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();
}
if(idx[0] != W) right[i][j][idx[0]] = 1;
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();
}
if(idx[0] != -1) down[idx[0]][j][i] = 1;
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();
}
if(idx[0] != H) down[i][j][idx[0]] = 1;
max.emplace_front(a[i][j]);
idx.emplace_front(i);
}
}
}
rep(i,0,H){
rep(j,0,W){
if(right[i][j].count(j+1)) right[i][j].erase(j+1);
if(down[i][j].count(i+1)) down[i][j].erase(i+1);
}
}
rep(i,0,H){
per(j,W-2,0){
for(auto &el: down[i][j]){
if(down[i][j+1].count(el.first)) el.second += down[i][j+1][el.first];
}
}
}
rep(j,0,W){
per(i,H-2,0){
for(auto &el: right[i][j]){
if(right[i+1][j].count(el.first)) el.second += right[i+1][j][el.first];
}
}
}
binary_indexed_tree bit(H+10);
rep(i,1,H-1){
rep(j,1,W-1){
vector<pii> query;
for(auto el: right[i][j-1]){
ll bottom = i+el.second;
// bottom 以下 かつ
ll lasting = el.first-j;
// lasting 以上
query.pb(mp(lasting, -bottom));
}
for(auto el: down[i-1][j]){
query.pb(mp(el.second, el.first));
}
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;
}
