#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];*/
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]);
}
rep(l,1,H-1){
rep(r,l,H-1){
if(right[r][j-1] <= k) break;
if(left[r][k+1] >= j) break;
if(up_state[r+1] < l && down_state[l-1] > r){
ans++;
}
}
}
}
}
return ans;
}
