#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
vector<int> fen;
void add(int i, int x){
for(i++; i < sz(fen); i+=i&-i) fen[i] += x;
}
int qry(int i){
int ans = 0;
for(i++; i > 0; i-=i&-i) ans += fen[i];
return ans;
}
int qry(int i, int j){
if(i > 0) return qry(j)-qry(i-1);
else return qry(j);
}
long long count_rectangles(vector<vector<int>> a) {
int n = sz(a), m = sz(a[0]);
vector<vector<int>> r1(n, vector<int>(m, -1)), r2(n, vector<int>(m, -1));
for(int i = 1; i < n-1; i++){
stack<pair<int, int>> st({{a[i][0], 0}});
for(int j = 1; j < m; j++){
while(!st.empty() && a[i][j] >= st.top().first){
auto [h, k] = st.top(); st.pop();
r2[i][k] = j-1;
}
if(!st.empty()) r1[i][j] = st.top().second+1;
st.emplace(a[i][j], j);
}
}
vector<vector<int>> c1(n, vector<int>(m, -1)), c2(n, vector<int>(m, -1));
for(int j = 1; j < m-1; j++){
stack<pair<int, int>> st({{a[0][j], 0}});
for(int i = 1; i < n; i++){
while(!st.empty() && a[i][j] >= st.top().first){
auto [h, k] = st.top(); st.pop();
c2[k][j] = i-1;
}
if(!st.empty()) c1[i][j] = st.top().second+1;
st.emplace(a[i][j], i);
}
}
fen.resize(max(n, m)+1);
vector<bool> valid(n*m);
vector<vector<tuple<int, int, int>>> byI(n*m), byJ(n*m);
set<tuple<int, int, int, int>> noDupl;
vector<set<int>> goodI(n*m), goodJ(n*m);
int q = 0;
for(int i = 1; i < n-1; i++){
for(int j = 1; j < m-1; j++){
// cerr << "\n" << i << " " << j << " " << r1[i][j] << " " << r2[i][j] << " " << c1[i][j] << " " << c2[i][j] << "\n";
if(c1[i][j] != -1 && c2[i][j] != -1) goodJ[c1[i][j]*n + c2[i][j]].insert(j);
if(r1[i][j] != -1 && r2[i][j] != -1) goodI[r1[i][j]*m + r2[i][j]].insert(i);
if(r1[i][j] != -1 && r2[i][j] != -1 && c1[i][j] != -1 && c2[i][j] != -1){
auto t = make_tuple(r1[i][j], r2[i][j], c1[i][j], c2[i][j]);
if(noDupl.count(t)) continue;
noDupl.insert(t);
valid[q] = true;
byI[c1[i][j]*n + c2[i][j]].emplace_back(r1[i][j], r2[i][j], q);
byJ[r1[i][j]*m + r2[i][j]].emplace_back(c1[i][j], c2[i][j], q);
q++;
}
}
}
for(int L = 1; L < n-1; L++){
for(int R = L; R < n-1; R++){
// cerr << "# " << L << " " << R << "\n";
for(int j : goodJ[L*n+R]){
// cerr << j << "\n";
add(j, 1);
}
for(auto [a, b, ind] : byI[L*n+R]){
// cerr << a << " " << b << " " << qry(a, b) << "\n";
if(qry(a, b) != b-a+1) valid[ind] = false;
}
for(int j : goodJ[L*n+R]){
add(j, -1);
}
}
}
for(int L = 1; L < m-1; L++){
for(int R = L; R < m-1; R++){
for(int i : goodI[L*m+R]){
add(i, 1);
}
for(auto [a, b, ind] : byJ[L*m+R]){
if(qry(a, b) != b-a+1) valid[ind] = false;
}
for(int i : goodI[L*m+R]){
add(i, -1);
}
}
}
int ans = 0;
for(bool b : valid) ans += b;
return ans;
}
