#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009
#define HEIGHT 7000005
template<class T> struct Seg {
const T ID = -INF; // comb(ID,b) must equal b, and maximum is less than 1e9
T comb(T a, T b) { return max(a, b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n, -INF); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T value) { // set value at position p
seg[p += n] = value;
for (p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r) { // minimum on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
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;
}
};
long long count_rectangles(vector<vector<int>> grid) {
int n = grid.size(), m = grid[0].size();
if(n <= 2 || m <= 2) return 0;
vector<int> leftEnd[n][m];
vector<int> topEnd[n][m];
int leftGreater[n][m];
int topGreater[n][m];
Seg<int> leftTree;
Seg<int> topTree;
leftTree.init(HEIGHT);
topTree.init(HEIGHT);
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(j == 0) leftGreater[i][j] = -INF;
else leftGreater[i][j] = leftTree.query(grid[i][j]+1, HEIGHT-1);
leftTree.upd(grid[i][j], j);
}
for(int j = 0; j<m; j++){
leftTree.upd(grid[i][j], -INF);
}
}
for(int j = 0; j<m; j++){
for(int i = 0; i<n; i++){
if(i == 0) topGreater[i][j] = -INF;
else topGreater[i][j] = topTree.query(grid[i][j]+1, HEIGHT-1);
topTree.upd(grid[i][j], i);
}
for(int i = 0; i<n; i++){
topTree.upd(grid[i][j], -INF);
}
}
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(cur);
prev = cur;
cur = leftGreater[i][cur];
}
sort(leftEnd[i][j].begin(), leftEnd[i][j].end());
reverse(leftEnd[i][j].begin(), leftEnd[i][j].end());
}
}
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(cur);
prev = cur;
cur = topGreater[cur][j];
}
}
}
long long ans = 0;
map<pair<int, pair<int, int>>, int> leftMP;
map<pair<int, pair<int, int>>, int> topMP;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
for(auto x : leftEnd[i][j]) leftMP[{i, {x, j}}] = leftMP[{i-1, {x, j}}]+1;
}
}
for(int j = 0; j<m; j++){
for(int i = 0; i<n; i++){
for(auto x : topEnd[i][j]) topMP[{j, {x, i}}] = topMP[{j-1, {x, i}}]+1;
}
}
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-topMP[{j-1, {x, i+1}}], x});
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+1){
tree.add(tmp[ind].second, -1);
ind--;
}
if(ind < 0) break;
ans += tree.sum(i-leftMP[{i, {x, j}}], i+1);
}
while(ind >= 0){
tree.add(tmp[ind].second, -1);
ind--;
}
}
}
return ans;
}
