题目描述

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

$$\sum_{l=1}^{n}\sum_{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.$$

也就是说，对每个子数组，求其中最大值除以最小值的整数商，再把所有结果求和。

输入格式

第一行输入整数 $n$。

$$1\le n\le 300000$$

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

$$1\le a_i\le 300000$$

保证所有 $a_i$ 互不相同。

输出格式

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

样例

6
1 3 6 4 2 5

56