小约翰向阿姨借了几百次膨胀螺丝后,阿姨最终决定把没用过的膨胀螺丝拿回来。但由于它们是家居设计的重要组成部分,小约翰决定把一些膨胀螺丝藏在最遥不可及的地方——环保木饰面下面。
给定一个整数序列 $$$a_1, a_2, \ldots, a_n$$$ 和一个段 $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$)。
您必须对序列执行以下操作一次。
- 选择序列$$$a$$$的任意子序列$$$^{\text{*}}$$$,并将其反转。请注意,子序列不必是连续的。
正式地,选择任意数量的索引 $$$i_1,i_2,\ldots,i_k$$$ 使得 $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$。然后,同时将所有 $$$1 \le x \le k$$$ 的第 $$$i_x$$$ 个元素更改为第 $$$i_{k-x+1}$$$ 个元素的原始值。
执行运算后求 $$$a_l+a_{l+1}+\ldots+a_{r-1}+a_r$$$ 的最小值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$l$$$、$$$r$$$ ($$$1 \le l \le r \le n \le 10^5$$$) — $$$a$$$ 的长度和段 $$$[l,r]$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_{i} \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单独的行上输出 $$$a_l+a_{l+1}+\ldots+a_{r-1}+a_r$$$ 的最小值。
示例
输入 #1
6 2 1 1 2 1 3 2 3 1 2 3 3 1 3 3 1 2 4 2 3 1 2 2 2 5 2 5 3 3 2 3 5 6 1 3 3 6 6 4 3 2
输出 #1
1 3 6 3 11 8
注意
在第二个测试用例中,数组为 $$$a=[1,2,3]$$$,段为 $$$[2,3]$$$。
选择子序列$$$a_1,a_3$$$并将其反转后,序列变为$$$[3,2,1]$$$。然后,总和 $$$a_2+a_3$$$ 变为 $$$3$$$。可以证明总和的最小可能值为$$$3$$$。