### 题解

$$x\in [L[i],i), y\in (i,R[i]],a[x]\times a[y] \leq a[i]$$

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 100005
#define M 4000005
int n, a[N], b[N], L[N], R[N], sta[N], top, tot;
ll ans;
std::vector<int> q[N];
inline int id (int x) {return x < b[1] ? 0 : std::lower_bound(b + 1, b + tot + 1, x) - b;}
int c[N];
inline int query (int x) {int ret = 0; for (; x; x -= lowbit(x)) ret += c[x]; return ret;}
inline void add (int x) {for (; x <= tot; x += lowbit(x)) c[x] += 1;}
int main ()
{
scanf("%d", &n);
fo (i, 1, n)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sta[top = 0] = 0;
fo (i, 1, n)
{
while (top && a[sta[top]] < a[i]) --top;
L[i] = sta[top] + 1;
sta[++top] = i;
}
sta[top = 0] = n + 1;
fd (i, n, 1)
{
while (top && a[sta[top]] <= a[i]) --top;
R[i] = sta[top] - 1;
sta[++top] = i;
}
fo (i, 1, n)
if (i - L[i] <= R[i] - i)
{
fo (j, L[i], i)
{
q[R[i]].pb(a[i] / a[j]);
q[i - 1].pb(-a[i] / a[j]);
}
}
else
{
fo (j, i, R[i])
{
q[i].pb(a[i] / a[j]);
q[L[i] - 1].pb(-a[i] / a[j]);
}
}
std::sort(b + 1, b + n + 1);
fo (i, 1, n) if (b[i] != b[tot]) b[++tot] = b[i];
fo (i, 1, n)
{
int sz = q[i].size() - 1;
fo (j, 0, sz)
{
int pos = std::upper_bound(b + 1, b + tot + 1, q[i][j] < 0 ? -q[i][j] : q[i][j]) - b - 1;
ans += q[i][j] < 0 ? -query(pos) : query(pos);
}
}
printf("%lld\n", ans);
return 0;
}