Description

给定一个长度为 $n$ 的数组 $a$，数组中的元素均为互不相同的正整数。计算

$$\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} \left\lfloor\frac{\max(a_{l},a_{l+1},\ldots,a_{r})}{\min(a_{l},a_{l+1},\ldots,a_{r})}\right\rfloor$$

其中，$\lfloor x \rfloor$ 表示对 $x$ 向下取整。

也就是说，需要计算数组 $a$ 的所有子数组中，最大值除以最小值的整数部分之和。

Input Format

输入的第一行包含一个整数 $n$，表示数组的长度（$1 \leq n \leq 300\,000$）。

输入的第二行包含 $n$ 个整数，表示数组 $a$（$1 \leq a_{i} \leq 300\,000$）。

保证数组 $a$ 中所有的数互不相同。

Output Format

输出一个整数，表示所求的和。

6
1 3 6 4 2 5

56

Hint

让我们更详细地考虑这个例子：

:::align{center} :::

由 ChatGPT 4.1 翻译