#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009
#define HEIGHT 7000005
struct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
struct Point{
int ind, num;
Point(){}
Point(int ii, int nn){
ind = ii, num = nn;
}
};
long long count_rectangles(vector<vector<int>> grid) {
int n = grid.size(), m = grid[0].size();
if(n <= 2 || m <= 2) return 0;
vector<Point> leftEnd[n][m];
vector<Point> topEnd[n][m];
int leftGreater[n][m];
int topGreater[n][m];
stack<pair<int, int>> leftST;
stack<pair<int, int>> topST;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
while(!leftST.empty() && grid[i][j] >= leftST.top().first) leftST.pop();
if(leftST.empty()) leftGreater[i][j] = -INF;
else leftGreater[i][j] = leftST.top().second;
leftST.push({grid[i][j], j});
}
while(!leftST.empty()) leftST.pop();
}
for(int j = 0; j<m; j++){
for(int i = 0; i<n; i++){
while(!topST.empty() && grid[i][j] >= topST.top().first) topST.pop();
if(topST.empty()) topGreater[i][j] = -INF;
else topGreater[i][j] = topST.top().second;
topST.push({grid[i][j], i});
}
while(!topST.empty()) topST.pop();
}
for(int i = 0; i<n; i++){
for(int j = 1; j<m; j++){
int cur = leftGreater[i][j-1];
int prev = j-1;
while(cur != -INF && grid[i][prev] < grid[i][j]){
leftEnd[i][j].push_back(Point(cur, 0));
prev = cur;
cur = leftGreater[i][cur];
}
}
}
for(int j = 0; j<m; j++){
for(int i = 1; i<n; i++){
int cur = topGreater[i-1][j];
int prev = i-1;
while(cur != -INF && grid[prev][j] < grid[i][j]){
topEnd[i][j].push_back(Point(cur, 0));
prev = cur;
cur = topGreater[cur][j];
}
}
}
long long ans = 0;
for(int j = 0; j<m; j++){
int occur[m];
int poccur[m];
fill(occur, occur+m, 0);
fill(poccur, poccur+m, 0);
for(int i = 0; i<n; i++){
if(i != 0){
for(auto x : leftEnd[i-1][j]) poccur[x.ind] = occur[x.ind];
}
for(auto &x : leftEnd[i][j]){
x.num = occur[x.ind]+1;
occur[x.ind]++;
}
if(i != 0){
for(auto x : leftEnd[i-1][j]) if(occur[x.ind] == poccur[x.ind]) occur[x.ind] = poccur[x.ind] = 0;
}
}
}
for(int i = 0; i<n; i++){
int occur[n];
int poccur[n];
fill(occur, occur+n, 0);
fill(poccur, poccur+n, 0);
for(int j = 0; j<m; j++){
if(j != 0){
for(auto x : topEnd[i][j-1]) poccur[x.ind] = occur[x.ind];
}
for(auto &x : topEnd[i][j]){
x.num = occur[x.ind]+1;
occur[x.ind]++;
}
if(j != 0){
for(auto x : topEnd[i][j-1]) if(occur[x.ind] == poccur[x.ind]) occur[x.ind] = poccur[x.ind] = 0;
}
}
}
FenwickTree tree(n);
for(int i = 1; i<n-1; i++){
for(int j = 2; j<m; j++){
// if(i != 4 || j != 4) continue;
if(leftEnd[i][j].empty()) continue;
if(topEnd[i+1][j-1].empty()) continue;
vector<pair<int, int>> tmp;
for(auto x : topEnd[i+1][j-1]) tmp.push_back({j-x.num, x.ind});
sort(tmp.begin(), tmp.end());
int ind = tmp.size()-1;
for(auto x : tmp) tree.add(x.second, 1);
for(auto x : leftEnd[i][j]){
while(ind >= 0 && tmp[ind].first > x.ind+1){
tree.add(tmp[ind].second, -1);
ind--;
}
if(ind < 0) break;
ans += tree.sum(i-x.num, i+1);
}
while(ind >= 0){
tree.add(tmp[ind].second, -1);
ind--;
}
}
}
return ans;
}
