#include "rect.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
class BIT {
int n;
vl v;
ll sum(int i) {
i++;
ll res = 0;
while (i >= 1) {
res += v[i];
i -= i & -i;
}
return res;
}
public:
BIT(int n) : n(n), v(n + 1) {}
void add(int i, int x) {
assert(0 <= i and i < n);
i++;
while (i <= n) {
v[i] += x;
i += i & -i;
}
}
ll sum(int l, int r) {
assert(0 <= l and l <= r and r <= n);
return sum(r - 1) - sum(l - 1);
}
};
ll count_rectangles(vvi a) {
int n = a.size(), m = a[0].size();
if (n < 3 or m < 3) return 0;
vvvi col_fix(m, vvi(m));
rep2(i, 1, n - 1) {
stack<int> st;
rep(j, m) {
while (!st.empty() and a[i][st.top()] < a[i][j]) {
if (st.top() < j - 1) col_fix[st.top() + 1][j - 1].pb(i);
st.pop();
}
if (!st.empty()) {
if (st.top() < j - 1) col_fix[st.top() + 1][j - 1].pb(i);
if (a[i][st.top()] == a[i][j]) st.pop();
}
st.push(j);
}
}
vvvi row_fix(n, vvi(n));
rep2(i, 1, m - 1) {
stack<int> st;
rep(j, n) {
while (!st.empty() and a[st.top()][i] < a[j][i]) {
if (st.top() < j - 1) row_fix[st.top() + 1][j - 1].pb(i);
st.pop();
}
if (!st.empty()) {
if (st.top() < j - 1) row_fix[st.top() + 1][j - 1].pb(i);
if (a[st.top()][i] == a[j][i]) st.pop();
}
st.push(j);
}
}
// {bottom, right} -> {left, top}
map<P, vp> mp;
rep(i, m) rep(j, m) {
int pre = -1, cnt = 0;
for (int k : col_fix[i][j]) {
if (pre + 1 < k) cnt = 0;
cnt++;
mp[{k, j}].eb(i, k - cnt + 1);
pre = k;
}
}
map<P, vp> rq;
rep(i, n) rep(j, n) {
int pre = -1, cnt = 0;
for (int k : row_fix[i][j]) {
if (pre + 1 < k) cnt = 0;
cnt++;
const vp &v = mp[{j, k}];
rq[{j, k}].eb(k - cnt + 1, i);
pre = k;
}
}
ll ans = 0;
BIT cnt(n);
// BIT sum(n);
for (auto &[p, v] : mp) {
if (!rq.count(p)) continue;
if(v.empty()) continue;
vp &cur = rq[p];
// cerr << p.first << ' ' << p.second << endl;
// for(auto [i,j] : v) cerr << "v " << i << ' ' << j << endl;
// for(auto [i,j] : cur) cerr << "c " << i << ' ' << j << endl;
int it = cur.size() - 1;
while (it >= 0 and cur[it].first > v.back().first) it--;
rrep(i, v.size()) {
cnt.add(v[i].second, 1);
// sum.add(v[i].second, v[i].first + 1);
while (it >= 0 and (i == 0 or cur[it].first > v[i - 1].first)) {
// ans += sum.sum(0, cur[it].second + 1);
// ans -= cnt.sum(0, cur[it].second + 1) * cur[it].first;
ans += cnt.sum(0, cur[it].second + 1);
it--;
}
}
rep(i, v.size()) {
cnt.add(v[i].second, -1);
// sum.add(v[i].second, -v[i].first - 1);
}
// cerr << ans << endl;
}
return ans;
}
