Чмяяякс на префиксе

Дан массив $a_1,a_2,\dots ,a_n$, состоящий из $n$ целых чисел. Вам нужно выполнить следующие шаги в заданном порядке:

• Выберите некоторый индекс $k$ $(1\le k\le n-1)$.

• Разделите массив $a$ на две части: $a_1,a_2,\dots ,a_k$ и $a_{k+1},a_{k+2},\dots ,a_n$.

• Удалите один элемент из каждой части.

Пусть $c$ - сумма элементов первой полученной части, а $d$ - сумма элементов второй части. Вам нужно найти максимальное возможное значение $|c-d|$. Иными словами, ваша задача - найти максимальную возможную разницу между суммами полученных частей после выполнения этих шагов.

Вы можете предположить, что сумма элементов пустой части равна $0$.

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

В первой строке находится одно целое число $n$ $(2\le n\le 10^5)$ - количество элементов в массиве $a$.

Во второй строке находятся $n$ целых чисел $a_i$ $(-10^3\le a_i\le 10^3)$ - элементы массива.

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

В первой и единственной строке вам нужно вывести одно целое число - максимальную возможную разницу между суммами полученных частей после выполнения таких шагов.

Примеры

Примечание

В первом примере, единственный способ разделить массив - взять $k=1$, т.е. создать два подмассива $[1]$ и $[2]$. Поскольку оба они состоят из одного элемента, единственный способ удалить один элемент из каждого подмассива - удалить оба. Таким образом, подмассивы становятся пустыми, их суммы становятся $0$, следовательно, ответ - $|0-0|=0$.

Во втором примере существует $10$ способов выполнения операций:

1. $[2],[-5,4,-7]$ -> $[],[4,-7]$ -> результат $|0-(4+(-7))|=|0-(-3)|=3$;

2. $[2],[-5,4,-7]$ -> $[],[-5,-7]$ -> результат $|0-(-5+(-7))|=12$;

3. $[2],[-5,4,-7]$ -> $[],[-5,4]$ -> $|0-(-5+4)|=1$;

4. $[2,-5],[4,-7]$ -> $[-5],[-7]$ -> $|(-5)-(-7)|=2$;

5. $[2,-5],[4,-7]$ -> $[-5],[4]$ -> $|(-5)-(4)|=9$;

6. $[2,-5],[4,-7]$ -> $[2],[-7]$ -> $|(2)-(-7)|=9$;

7. $[2,-5],[4,-7]$ -> $[2],[4]$ -> $|(2)-(4)|=2$;

8. $[2],[-5,4,-7]$ -> $[],[4,-7]$ -> $|0-(4+(-7))|=3$;

9. $[2],[-5,4,-7]$ -> $[],[-5,-7]$ -> $|0-(-5+(-7))|=12$;

10. $[2],[-5,4,-7]$ -> $[],[-5,4]$ -> $|0-(-5+4)|=1$.

Как мы можем заметить, максимальное возможное значение здесь - $12$, которое можно получить, взяв $k=2$ и оставив $-5$ из первого полученного подмассива и $-7$ из второго.

В третьем примере не имеет значения, как мы разделим массив или какой элемент мы удалим из них - сумма любого из полученных подмассивов всегда будет $0$, а также разница между ними.

Оценивание

1. ($4$ балла): $n\le 3$;

2. ($4$ балла): все элементы массива равны ($a_i=a_j$ для всех $1\le i,j\le n$);

3. ($5$ баллов): все элементы массива положительны ($a_i>0$ для всех $1\le i\le n$);

4. ($7$ баллов): массив неубывающий ($a_i\le a_j$ для всех $1\le i<j\le n$);

5. ($10$ баллов): $n\le 300$;

6. ($10$ баллов): $n\le 2000$;

7. ($10$ баллов): нет дополнительных ограничений.