题目描述

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

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

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

输入

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

第二行输入 n 个整数$a_1, a_2, · · · , 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。

样例 2/3/4

stone1.in stone1.ans

stone2.in stone2.ans

stone3.in stone3.ans

数据规模与约定

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

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

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

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

对于 100% 的数据，有 $1 ≤ l ≤ r ≤ n ≤ 10^5 , 1 ≤ a_i ≤ 10^8$。保证 $a_i$ 随机。

随机方式 为：先选择一个所有 $a_i$ 的上界 $v$，对于每个 $a_i$，它在 $[1, v]$ 中的所有整数中等概率随机 选取一个。