#P15868. [Roi2024 Team]Nightmare Sum噩梦之和

    ID: 15079 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-贡献法单调栈计算区间贡献倍数枚举补集计数普通线段树线段树上二分

[Roi2024 Team]Nightmare Sum噩梦之和

题目描述

给定一个长度为 nn 的数组 aa,其中元素是互不相同的正整数。请计算

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

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

输入格式

第一行输入整数 nn。

1≤n≤3000001\le n\le 300000

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

1≤ai≤3000001\le a_i\le 300000

保证所有 aia_i 互不相同。

输出格式

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

样例

6
1 3 6 4 2 5
56