Subsequence Update
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, data structures, greedy, sortings

After Little John borrowed expansion screws from auntie a few hundred times, eventually she decided to come and take back the unused ones.But as they are a crucial part of home design, Little John decides to hide some in the most unreachable places — under the eco-friendly wood veneers.

You are given an integer sequence $$$a_1, a_2, \ldots, a_n$$$, and a segment $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$).

You must perform the following operation on the sequence exactly once.

- Choose any subsequence$$$^{\text{∗}}$$$ of the sequence $$$a$$$, and reverse it. Note that the subsequence does not have to be contiguous.

Formally, choose any number of indices $$$i_1,i_2,\ldots,i_k$$$ such that $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$. Then, change the $$$i_x$$$-th element to the original value of the $$$i_{k-x+1}$$$-th element simultaneously for all $$$1 \le x \le k$$$.

Find the minimum value of $$$a_l+a_{l+1}+\ldots+a_{r-1}+a_r$$$ after performing the operation.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n \le 10^5$$$) — the length of $$$a$$$, and the segment $$$[l,r]$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_{i} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output the minimum value of $$$a_l+a_{l+1}+\ldots+a_{r-1}+a_r$$$ on a separate line.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
On the second test case, the array is $$$a=[1,2,3]$$$ and the segment is $$$[2,3]$$$.

After choosing the subsequence $$$a_1,a_3$$$ and reversing it, the sequence becomes $$$[3,2,1]$$$. Then, the sum $$$a_2+a_3$$$ becomes $$$3$$$. It can be shown that the minimum possible value of the sum is $$$3$$$.

Example input:
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

Example output:
1
3
6
3
11
8

Editorial:
To solve this problem, it is important to observe and prove the following claim:
• Claim: It is not beneficial to choose indices $$$i<l$$$ and $$$j>r$$$ at the same time.
Notice that we only care about values that end up on indices in $$$[l,r]$$$.
If we choose $$$i_1,i_2,\ldots,i_k$$$ such that $$$i_1<l$$$ and $$$i_k>r$$$, $$$i_1$$$ and $$$i_k$$$ will be swapped with each other and not change the values that end up on $$$[l,r]$$$. This means we can exchange it for a shorter sequence of indices $$$i_2,i_3,\ldots,i_{k-1}$$$, preserving the values ending up on $$$[l,r]$$$. If we repeat this exchange until it is no longer possible, it will satisfy either:
• Every index $$$i$$$ is in $$$[l,n]$$$;
• or every index $$$i$$$ is in $$$[1,r]$$$.
We can solve for both cases separately. For either case, we can constructively show that we can get the minimum $$$r-l+1$$$ values in the subsegment into $$$[l,r]$$$. The proof is as follows:
WLOG assume we are solving for $$$[1,r]$$$, and the indices of the $$$k=r-l+1$$$ minimum values are $$$j_1,j_2,\ldots,j_k$$$. Then:
• If we select every index in $$$[l,r]$$$ not one of the minimum $$$k$$$ values, there will be $$$x$$$ of them.
• If we select every index outside $$$[l,r]$$$ which is one of the minimum $$$k$$$ values, there will be also $$$x$$$ of them.
Thus, we end up with a subsequence of length $$$2x$$$, that gets the minimum $$$k$$$ values into the subsegment $$$[l,r]$$$. As a result, we only have to find the minimum $$$k$$$ values of the subsegment. This can be done easily with sorting. Do this for both $$$[1,r]$$$ and $$$[l,n]$$$, and we get the answer.
The problem has been solved with time complexity $$$\mathcal{O}(n \log n)$$$ per test case, due to sorting.