부분수열 갱신

Little John이 숙모에게서 확장 나사를 수백 번 빌렸는데, 결국 숙모가 쓰지 않는 나사를 돌려받으러 오기로 했다.

나사는 집 설계에서 중요한 부품이라서, Little John은 아무도 닿을 수 없는 곳, 즉 친환경 목재 化粧판 아래에 나사를 숨기기로 했다.

정수 수열 $a_1, a_2, \ldots, a_n$과 구간 $[l,r]$ ($1 \le l \le r \le n$)이 주어진다.

이 수열에 대해 다음 연산을 정확히 한 번 수행해야 한다.

• 수열 $a$의 임의의 부분수열을 골라 뒤집는다. 부분수열은 연속일 필요가 없다.

형식적으로는 $1 \le i_1 < i_2 < \ldots < i_k \le n$을 만족하는 임의의 인덱스 $i_1, i_2, \ldots, i_k$를 고른다. 그다음 모든 $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$)이 주어진다. $n$은 $a$의 길이이고 $[l,r]$은 구간이다.

둘째 줄에는 정수 $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$의 최솟값을 한 줄에 출력한다.

두 번째 테스트 케이스에서 $a=[1,2,3]$이고 구간은 $[2,3]$이다. 부분수열 $a_1, a_3$을 골라 뒤집으면 수열은 $[3,2,1]$이 된다. 그러면 $a_2+a_3$은 $3$이 된다. 합의 최솟값이 $3$임을 보일 수 있다.