#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;
}
}
for (auto &[p, v] : mp) sort(all(v));
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}];
int it = lower_bound(all(v), P{k - cnt + 1, -1}) - v.begin();
if (it < v.size()) {
rq[{j, k}].eb(it, i);
}
pre = k;
}
}
ll ans = 0;
BIT bt(n);
for (auto &[p, v] : mp) {
if (!rq.count(p)) continue;
vp &cur = rq[p];
int it = cur.size() - 1;
rrep(i, v.size()) {
bt.add(v[i].second, 1);
while (it >= 0 and cur[it].first == i) {
ans += bt.sum(0, cur[it].second + 1);
it--;
}
}
rep(i, v.size()) {
bt.add(v[i].second, -1);
}
}
return ans;
}
