#include "rect.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
vector<vector<bool> > good(m, vector<bool>(m, 0));
ll ret = 0;
for (int u = 1;u < n - 1;u++) {
vector<int> ma(m, 0);
vector<pii> p;
for (int d = u;d < n - 1;d++) {
int lef = 0;
stack<int> stk;
vector<pii> nxt;
for (int i = 0;i < m;i++) {
auto add = [&] (int l, int r) {
if (l+1 < r) {
if (l >= lef && (u == d || good[l][r])) {
ret++;
}
if (u == d) nxt.push_back({l, r});
else if (good[l][r]) nxt.push_back({l, r});
}
};
bool check = 1;
while (stk.size() && a[d][i] >= a[d][stk.top()]) {
int l = stk.top();
add(l, i);
if (a[d][l] == a[d][i]) check = 0;
stk.pop();
}
if (check && stk.size()) {
add(stk.top(), i);
}
stk.push(i);
ma[i] = max(ma[i], a[d][i]);
if (ma[i] >= a[u-1][i] || ma[i] >= a[d+1][i]) {
lef = i;
}
}
for (auto x:p) good[x.ff][x.ss] = 0;
p = nxt;
for (auto x:p) good[x.ff][x.ss] = 1;
//for (auto x:p) debug(x.ff, x.ss);
//debug();
}
for (auto x:p) good[x.ff][x.ss] = 0;
}
return ret;
}
