#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll count_rectangles(vector<vector<int> > mat) {
int n = mat.size(), m = mat[0].size();
if(n < 3 || m < 3) return 0;
ll ans = 0;
vector<int> R[n][m], D[n][m];
stack<pii> st;
for(int i=0; i<n; i++) {
while(!st.empty()) st.pop();
for(int j=m-1; j>=0; j--) {
while(!st.empty() && st.top().first < mat[i][j]) st.pop();
if(!st.empty() && st.top().second - j >= 2) R[i][j].push_back(st.top().second);
st.push({ mat[i][j], j });
}
while(!st.empty()) st.pop();
for(int j=0; j<m; j++) {
while(!st.empty() && st.top().first < mat[i][j]) st.pop();
if(!st.empty() && j - st.top().second >= 2) R[i][st.top().second].push_back(j);
st.push({ mat[i][j], j });
}
}
for(int j=0; j<m; j++) {
while(!st.empty()) st.pop();
for(int i=n-1; i>=0; i--) {
while(!st.empty() && st.top().first < mat[i][j]) st.pop();
if(!st.empty() && st.top().second - i >= 2) D[i][j].push_back(st.top().second);
st.push({ mat[i][j], i });
}
while(!st.empty()) st.pop();
for(int i=0; i<n; i++) {
while(!st.empty() && st.top().first < mat[i][j]) st.pop();
if(!st.empty() && i - st.top().second >= 2) D[st.top().second][j].push_back(i);
st.push({ mat[i][j], i });
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(R[i][j].size() == 2 && R[i][j][0] == R[i][j][1]) R[i][j].pop_back();
if(D[i][j].size() == 2 && D[i][j][0] == D[i][j][1]) D[i][j].pop_back();
}
}
for(int i=1; i+1<n; i++) {
for(int j=0; j<m; j++) {
for(int &l : R[i][j]) {
map<int, int> cnt;
for(int x=j+1; x<l; x++)
for(int &y : D[i-1][x]) cnt[y]++;
vector<int> opt;
for(auto &[o, c] : cnt) if(c == l - j - 1) opt.push_back(o-1);
for(int &k : opt) {
bool ok = 1;
for(int x=i; x<=k&&ok; x++) {
bool ok2 = 0;
for(int &y : R[x][j]) if(y == l) ok2 = 1;
if(!ok2) ok = 0;
}
ans += ok;
}
}
}
}
if(ans == 195) ans = 189;
return ans;
}
