给定一个长度为 $n$ 且由互不相同的正整数组成的数组 $a$。计算：
$$\sum_{l=1}^{n} \sum_{r=l}^{n} \left\lfloor \frac{\max(a_l, a_{l+1}, \dots, a_r)}{\min(a_l, a_{l+1}, \dots, a_r)} \right\rfloor$$
这里，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数（向下取整）。
因此，需要计算数组 $a$ 的所有子数组中，最大值整除最小值之商的和。
输入格式
输入的第一行包含一个整数 $n$ — 数组的长度（$1 \le n \le 300\,000$）。
输入的第二行包含 $n$ 个整数 — 数组 $a$（$1 \le a_i \le 300\,000$）。
保证数组 $a$ 中的所有数字互不相同。
输出格式
输出一个整数 — 所求的和。
样例
输入样例 1
6 1 3 6 4 2 5
输出样例 1
56
说明
让我们更详细地分析这个样例：
| $[l, r]$ | $a[l\dots r]$ | $\min$ | $\max$ | $\lfloor \frac{\max}{\min} \rfloor$ |
|---|---|---|---|---|
| $[1, 1]$ | $[1]$ | $1$ | $1$ | $1$ |
| $[1, 2]$ | $[1, 3]$ | $1$ | $3$ | $3$ |
| $[1, 3]$ | $[1, 3, 6]$ | $1$ | $6$ | $6$ |
| $[1, 4]$ | $[1, 3, 6, 4]$ | $1$ | $6$ | $6$ |
| $[1, 5]$ | $[1, 3, 6, 4, 2]$ | $1$ | $6$ | $6$ |
| $[1, 6]$ | $[1, 3, 6, 4, 2, 5]$ | $1$ | $6$ | $6$ |
| $[2, 2]$ | $[3]$ | $3$ | $3$ | $1$ |
| $[2, 3]$ | $[3, 6]$ | $3$ | $6$ | $2$ |
| $[2, 4]$ | $[3, 6, 4]$ | $3$ | $6$ | $2$ |
| $[2, 5]$ | $[3, 6, 4, 2]$ | $2$ | $6$ | $3$ |
| $[2, 6]$ | $[3, 6, 4, 2, 5]$ | $2$ | $6$ | $3$ |
| $[3, 3]$ | $[6]$ | $6$ | $6$ | $1$ |
| $[3, 4]$ | $[6, 4]$ | $4$ | $6$ | $1$ |
| $[3, 5]$ | $[6, 4, 2]$ | $2$ | $6$ | $3$ |
| $[3, 6]$ | $[6, 4, 2, 5]$ | $2$ | $6$ | $3$ |
| $[4, 4]$ | $[4]$ | $4$ | $4$ | $1$ |
| $[4, 5]$ | $[4, 2]$ | $2$ | $4$ | $2$ |
| $[4, 6]$ | $[4, 2, 5]$ | $2$ | $5$ | $2$ |
| $[5, 5]$ | $[2]$ | $2$ | $2$ | $1$ |
| $[5, 6]$ | $[2, 5]$ | $2$ | $5$ | $2$ |
| $[6, 6]$ | $[5]$ | $5$ | $5$ | $1$ |