Codeforces Round 815 (Div. 2) |
---|
Закончено |
Дан массив $$$a$$$ длины $$$n$$$. Вы можете выбрать любой подотрезок $$$a_l, a_{l + 1}, \ldots, a_r$$$ массива длины, не совпадающий со всем массивом, то есть, для которого $$$1 \le l \le r \le n$$$ и $$$r - l + 1 < n$$$. Красотой выбранного подоторезка назовем значение
$$$$$$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$$$$$
Найдите максимальную красоту подотрезка среди всех возможных допустимых подотрезков массива (за исключением всего массива).
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ $$$(4 \leq n \leq 10^5)$$$ — длину массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — элементы данного массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одно число — искомое максимальное значение красоты.
4 8 1 2 2 3 1 5 6 1 5 1 2 3 100 200 4 3 3 3 3 6 7 8 3 1 1 8
9 297 0 14
В первом тесте из условия оптимально выбрать отрезок $$$l = 7$$$, $$$r = 8$$$. Красота этого отрезка равна $$$(6 - 1) + (5 - 1) = 9$$$.
Во втором тесте из условия оптимально выбрать отрезок $$$l = 2$$$, $$$r = 4$$$. Красота этого отрезка равна $$$(100 - 2) + (200 - 1) = 297$$$.
Название |
---|