После того как Маленький Джон несколько сотен раз одалживал у тетушки шурупы для расширения, она решила прийти и забрать неиспользованные.Но поскольку они являются важной частью домашнего дизайна, Маленький Джон решает спрятать некоторые из них в самых недоступных местах — под экологически чистыми древесными фанерами.
Вам дана последовательность целых чисел \(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\) после выполнения операции.
Выходные данные
Для каждого тестового случая выведите минимальное значение \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
3
6
3
11
8
|