题目描述

Given an array $a$ of length $n$, consisting of distinct positive integers. Compute

$$\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 $$

Here, $\lfloor x \rfloor$ denotes $x$ rounded down to the nearest integer.

Thus, it is necessary to compute the sum of the results of integer division of the maximum by the minimum over all subarrays of the array $a$.

输入格式

The first line of input contains a single integer $n$~--- the length of the array $(1 \leq n \leq 300\,000)$.

The second line of input contains $n$ integers~--- the array $a$ $(1 \leq a_{i} \leq 300\,000)$.

It is guaranteed that all numbers in the array $a$ are distinct.

输出格式

Output a single number --- the desired sum.

6
1 3 6 4 2 5

56

提示

Let's consider the example in more detail:

:::align{center} :::