题目描述

在小约翰向阿姨借了几百次膨胀螺丝后，她最终决定来收回那些没用过的螺丝。

但由于膨胀螺丝是家居设计的重要组成部分，小约翰决定把它们藏在最难以触及的地方--环保木皮下面。

给你一个整数序列 $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 \lt i_2 \lt \ldots \lt 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$ 的最小值。

$^{\text{∗}}$ 如果 $b$ 可以从 $a$ 中删除任意位置上的几个（可能是零个或全部）元素而得到，则序列 $b$ 是序列 $a$ 的子序列。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ ）。( $1 \le a_{i} \le 10^9$ ).

保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每个测试用例，另起一行输出 $a_l+a_{l+1}+\ldots+a_{r-1}+a_r$ 的最小值。

说明/提示

在第二个测试用例中，数组为 $a=[1,2,3]$ ，段为 $[2,3]$ 。

选择子序列 $a_1,a_3$ 并将其反转后，序列变为 $[3,2,1]$ 。然后，和 $a_2+a_3$ 变为 $3$ 。由此可见，和的最小可能值为 $3$ 。

样例

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
3
6
3
11
8