#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll count_rectangles(vector<vector<int>> a){
int n = a.size(), m = a[0].size();
vector<vector<int>> l(n, vector<int>(m, -1)), r(n, vector<int>(m, -1)), u(n, vector<int>(m, -1)), d(n, vector<int>(m, -1));
stack<pair<int,int>> st;
for (int i=0; i<n; i++){
while (!st.empty()) st.pop();
for (int j=0; j<m; j++){
while (!st.empty() && st.top().first <= a[i][j]){
r[i][st.top().second] = j;
if (st.top().first == a[i][j]) l[i][j] = st.top().second;
st.pop();
}
if (!st.empty() && l[i][j] == -1) l[i][j] = st.top().second;
st.push({a[i][j], j});
}
}
for (int j=0; j<m; j++){
while (!st.empty()) st.pop();
for (int i=0; i<n; i++){
while (!st.empty() && st.top().first <= a[i][j]){
d[st.top().second][j] = i;
if (st.top().first == a[i][j]) u[i][j] = st.top().second;
st.pop();
}
if (!st.empty() && u[i][j] == -1) u[i][j] = st.top().second;
st.push({a[i][j], i});
}
}
vector<vector<int>> cand;
for (int i=1; i<n-1; i++){
for (int j=1; j<m-1; j++){
if (r[i][j-1] != -1){
if (d[i-1][r[i][j-1]-1] != -1) cand.push_back({i, d[i-1][r[i][j-1]-1]-1, j, r[i][j-1]-1});
if (u[i+1][r[i][j-1]-1] != -1) cand.push_back({u[i+1][r[i][j-1]-1]+1, i, j, r[i][j-1]-1});
if (d[i-1][j] != -1) cand.push_back({i, d[i-1][j]-1, j, r[i][j-1]-1});
if (u[i+1][j] != -1) cand.push_back({u[i+1][j]+1, i, j, r[i][j-1]-1});
}
if (l[i][j+1] != -1){
if (d[i-1][l[i][j+1]+1] != -1) cand.push_back({i, d[i-1][l[i][j+1]+1]-1, l[i][j+1]+1, j});
if (u[i+1][l[i][j+1]+1] != -1) cand.push_back({u[i+1][l[i][j+1]+1]+1, i, l[i][j+1]+1, j});
if (d[i-1][j] != -1) cand.push_back({i, d[i-1][j]-1, l[i][j+1]+1, j});
if (u[i+1][j] != -1) cand.push_back({u[i+1][j]+1, i, l[i][j+1]+1, j});
}
if (d[i-1][j] != -1){
if (r[d[i-1][j]-1][j-1] != -1) cand.push_back({i, d[i-1][j]-1, j, r[d[i-1][j]-1][j-1]-1});
if (l[d[i-1][j]-1][j+1] != -1) cand.push_back({i, d[i-1][j]-1, l[d[i-1][j]-1][j+1]+1, j});
if (r[i][j-1] != -1) cand.push_back({i, d[i-1][j]-1, j, r[i][j-1]-1});
if (l[i][j+1] != -1) cand.push_back({i, d[i-1][j]-1, l[i][j+1]+1, j});
}
if (u[i+1][j] != -1){
if (r[u[i+1][j]+1][j-1] != -1) cand.push_back({u[i+1][j]+1, i, j, r[u[i+1][j]+1][j-1]-1});
if (l[u[i+1][j]+1][j+1] != -1) cand.push_back({u[i+1][j]+1, i, l[u[i+1][j]+1][j+1]+1, j});
if (r[i][j-1] != -1) cand.push_back({u[i+1][j]+1, i, j, r[i][j-1]-1});
if (l[i][j+1] != -1) cand.push_back({u[i+1][j]+1, i, l[i][j+1]+1, j});
}
}
}
ll res = 0;
set<ll> done;
for (vector<int> v : cand){
int t = v[0], b = v[1], i = v[2], j = v[3];
ll idx = (ll)t+(ll)b*(ll)2500+(ll)i*(ll)pow(2500, 2)+(ll)j*(ll)pow(2500, 3);
if (done.find(idx) != done.end()) continue;
done.insert(idx);
if (b < t || j < i) continue;
bool valid = true;
for (int row=t; row<=b; row++){
if (r[row][i-1] != j+1 && l[row][j+1] != i-1) valid = false;
}
for (int col=i; col<=j; col++){
if (d[t-1][col] != b+1 && u[b+1][col] != t-1) valid = false;
}
if (valid) res++;
}
return res;
}
