#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
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<short>> r1(n, vector<short>(m, -1)), r2(n, vector<short>(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()) {
if(st.top().first > a[i][j]) r1[i][j] = st.top().second+1;
else r1[i][j] = r1[i][st.top().second];
}
st.emplace(a[i][j], j);
}
}
vector<vector<short>> c1(n, vector<short>(m, -1)), c2(n, vector<short>(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()){
if(st.top().first > a[i][j]) c1[i][j] = st.top().second+1;
else c1[i][j] = c1[st.top().second][j];
}
st.emplace(a[i][j], i);
}
}
a.clear();
a.shrink_to_fit();
int mx = max(n, m);
fen.resize(mx+1);
vector<bool> valid;
vector<vector<pair<int, int>>> byI(mx*mx);
unordered_set<ll> noDupl;
vector<vector<int>> goodI(mx*mx), goodJ(mx*mx);
int q = 0;
int ans = 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(r1[i][j] != -1 && r2[i][j] != -1 && c1[i][j] != -1 && c2[i][j] != -1){
int x = c1[i][j]*mx + c2[i][j], y = r1[i][j]*mx + r2[i][j];
goodJ[x].push_back(j);
goodI[y].push_back(i);
if(r1[i][j] == r2[i][j] && c1[i][j] == c2[i][j]){
ans++;
continue;
}
ll t = (ll)x*mx*mx+y;
if(noDupl.count(t)) continue;
noDupl.insert(t);
valid.push_back(true);
byI[x].emplace_back(y, q);
q++;
}
}
}
vector<bool> used(mx);
for(int id = 1; id < mx*mx; id++){
int added = 0;
for(int j : goodJ[id]){
if(!used[j]) add(j, 1), added++;
used[j] = true;
}
for(auto [id2, ind] : byI[id]){
int L = id2/mx, R = id2%mx;
if(added < R-L+1 || qry(L, R) != R-L+1) valid[ind] = false;
}
for(int j : goodJ[id]){
if(used[j]) add(j, -1);
used[j] = false;
}
}
noDupl = unordered_set<ll>();
goodJ = vector<vector<int>>();
vector<vector<pair<int, int>>> byJ(mx*mx);
for(int id = 1; id < mx*mx; id++){
for(auto [id2, ind] : byI[id]){
byJ[id2].emplace_back(id, ind);
}
}
for(int id = 1; id < mx*mx; id++){
int last = -1, added = 0;
for(int i : goodI[id]){
if(i != last) add(i, 1), added++;
last = i;
}
for(auto [id2, ind] : byJ[id]){
int L = id2/mx, R = id2%mx;
if(added < R-L+1 || qry(L, R) != R-L+1) valid[ind] = false;
}
last = -1;
for(int i : goodI[id]){
if(i != last) add(i, -1);
last = i;
}
}
for(bool b : valid) ans += b;
return ans;
}
