B. Обновление подпоследовательности
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того как Маленький Джон несколько сотен раз одалживал у тетушки шурупы для расширения, она решила прийти и забрать неиспользованные.

Но поскольку они являются важной частью домашнего дизайна, Маленький Джон решает спрятать некоторые из них в самых недоступных местах — под экологически чистыми древесными фанерами.

Вам дана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ и отрезок $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$).

Вы должны выполнить следующую операцию над последовательностью ровно один раз.

  • Выберите любую подпоследовательность$$$^{\text{∗}}$$$ последовательности $$$a$$$ и разверните её. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной.

Формально, выберите любое количество индексов $$$i_1,i_2,\ldots,i_k$$$ так, чтобы $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$. Затем одновременно измените $$$i_x$$$-й элемент на оригинальное значение $$$i_{k-x+1}$$$-го элемента для всех $$$1 \le x \le k$$$.

Найдите минимальное значение $$$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$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превышает $$$10^5$$$.

Выходные данные

Для каждого тестового случая выведите минимальное значение $$$a_l+a_{l+1}+\ldots+a_{r-1}+a_r$$$ в отдельной строке.

Пример
Входные данные
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
Примечание

Во втором тестовом случае массив $$$a=[1,2,3]$$$, а интервал $$$[2,3]$$$.

После выбора подпоследовательности $$$a_1,a_3$$$ и её разворота, последовательность становится $$$[3,2,1]$$$. Затем сумма $$$a_2+a_3$$$ становится равной $$$3$$$. Можно показать, что минимально возможное значение суммы равно $$$3$$$.