P13973 [VKOSHP 2024] Nightmare Sum
题目描述
给定一个长度为 $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$ 的所有子数组中，最大值除以最小值的整数部分之和。
输入格式
输入的第一行包含一个整数 $n$，表示数组的长度（$1 \leq n \leq 300\,000$）。
输入的第二行包含 $n$ 个整数，表示数组 $a$（$1 \leq a_{i} \leq 300\,000$）。
保证数组 $a$ 中所有的数互不相同。
输出格式
输出一个整数，表示所求的和。
说明/提示
让我们更详细地考虑这个例子：
:::align{center}
:::
由 ChatGPT 4.1 翻译