#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
const int MM = 2502;
int n, m, ans;
int first[MM], last[MM], bit[MM], stl;
std::pair<int, int> st[MM];
std::vector<std::pair<int, int>> vec(MM);
std::map<int, int, std::greater<int>> hor[MM][MM], vert[MM][MM];
void update(int i, int v){
for(; i < MM; i += i&-i)
bit[i] += v;
}
int query(int i){
int ret = 0;
for(; i; i -= i&-i)
ret += bit[i];
return ret;
}
long long count_rectangles(std::vector<std::vector<int>> a){
n = a.size(), m = a[0].size();
for(int i = 0; i < n; i++){
stl = 0;
for(int j = 0; j < m; j++){
//remove duplicates
while(stl && st[stl].first < a[i][j])
stl--;
first[j] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
st[++stl] = {a[i][j], j};
}
stl = 0;
for(int j = m-1; j >= 0; j--){
while(stl && st[stl].first <= a[i][j])
stl--;
last[j] = !stl ? -1 : st[stl].second;
st[++stl] = {a[i][j], j};
}
for(int j = 0; j < m; j++){
if(first[j] == -1 || last[j] == -1)
continue;
first[j]++, last[j]--;
hor[i][first[j]][last[j]] = 1;
}
}
for(int j = 0; j < m; j++){
stl = 0;
for(int i = 0; i < n; i++){
//remove duplicates
while(stl && st[stl].first < a[i][j])
stl--;
first[i] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
st[++stl] = {a[i][j], i};
}
stl = 0;
for(int i = n-1; i >= 0; i--){
while(stl && st[stl].first <= a[i][j])
stl--;
last[i] = !stl ? -1 : st[stl].second;
st[++stl] = {a[i][j], i};
}
for(int i = 0; i < n; i++){
if(first[i] == -1 || last[i] == -1)
continue;
first[i]++, last[i]--;
vert[first[i]][j][last[i]] = 1;
}
}
for(int i = n-1; i >= 0; i--){
for(int j = m-1; j >= 0; j--){
for(auto &x: hor[i][j])
if(hor[i+1][j].count(x.first))
x.second += hor[i+1][j][x.first];
for(auto &x: vert[i][j])
if(vert[i][j+1].count(x.first))
x.second += vert[i][j+1][x.first];
for(auto &x: hor[i][j])
vec.push_back({x.first-j+1, x.second}); //adjust
sort(vec.begin(), vec.end(), [](auto &x, auto &y){
return x.second > y.second;
});
int l = 0;
for(auto &b: vert[i][j]){
int bf = b.first-i+1;
while(l < vec.size() && bf <= vec[l].second)
update(vec[l++].first, 1);
ans += query(b.second);
}
while(l)
update(vec[--l].first, -1);
vec.clear();
}
}
return ans;
}
/*
* in a row, for every point, get 1st left > and 1st right greater
* this will get all possible
*
* using mono stack
*
*
* sort row segments
* starting at point i, on row j
* for each (i, r), dp for how long can go down
*
* then do same for vertical
*
* when it works is when: vert_seg <= dp_vert[hor_seg] and hor_seg <= dp_hor[vert_seg]
*
* sort hor and vert by y reversed
* loop through vert with l ptr for hor
* while hor[l] >= y, push hor[l++].x into bit
* answer += query_greater_than_equals(vert[i].x)
*
* vertical <= NM
* horizontal <= NM
* time complexity vert * log(hor) = NM log(NM)
*/
