题目描述

小可可面前有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个石子。小可可想要在开始选择一堆石子，然后从它开始，每次合并这堆石子左边的那堆石子或者右边的那堆石子。合并两堆石子个数为 $x, y$ 的石子堆需要花 $x + y$ 的力气，并且会合并成一堆 $x + y$ 个石子的石子堆。

小可可想花费最小的力气从最初选择的那堆石子开始，将所有石子都合并完。小可可想知道，如果他选择编号在 $[l, r]$ 里面的每一堆石子作为最初的石子，那么他将 $n$ 堆石子合并成一堆花的最小力气是多少。

小可可不想太为难你，所以他保证所有的 $a_i$ 是随机的。

输入格式

第一行输入一行三个整数 $n, l, r$，石子堆数和最开始选择的那堆石子的编号区间。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每堆石子的石子个数。

输出格式

输出一行 $r - l + 1$ 个整数，第 $i$ 个整数表示小可可选择编号为 $l - 1 + i$ 的石子堆作为最开始的那堆石子时，将所有石子都合并完花的最少力气。

4 1 4
5 1 3 1

25 19 19 19

提示

样例 1 解释

对于第 $1$ 堆石子作为初始的石子堆，最优（也是唯一）的合并策略是先合并第 $2$ 堆，再合并第 $3$ 堆，随后合并第 $4$ 堆，花费力气为 $25$；

对于第 $2$ 堆石子作为初始的石子堆，最优的合并策略是先合并第 $3$ 堆，再合并第 $4$ 堆，随后合并第 $1$ 堆，花费力气为 $19$；

对于第 $3$ 堆石子作为初始的石子堆，最优的合并策略是先合并第 $2$ 堆，再合并第 $4$ 堆，随后合并第 $1$ 堆，花费力气为 $19$；

对于第 $4$ 堆石子作为初始的石子堆，最优（也是唯一）的合并策略是先合并第 $3$ 堆，再合并第 $2$ 堆，随后合并第 $1$ 堆，花费力气为 $19$。

数据规模与约定

对于 $20 \%$ 的数据，满足 $n \leq 10$；

对于 $40 \%$ 的数据，满足 $n \leq 300$；

对于 $60 \%$ 的数据，满足 $n \leq 5000$；

对于另外 $20 \%$ 的数据，满足 $n \leq 10^5, r - l + 1 \leq 50$；

对于 $100 \%$ 的数据，有 $1 \leq l \leq r \leq n \leq 10^5, 1 \leq a_i \leq 10^8$。保证 $a_i$ 随机。随机方式为：先选择一个所有 $a_i$ 的上界 $v$，对于每个 $a_i$，它在 $[1, v]$ 中的所有整数中等概率随机选取一个。