Pref Suff Chmyaaax Diff

$n$ tam sayıdan ibarət $a_1,a_2,\dots ,a_n$ ardıcıllığı verilir. Aşağıdakı addımları verilmiş sıra ilə yerinə yetirməlisiniz:

• Bir indeksi $k$ $(1\le k\le n-1)$ seçin.

• Ardıcıllığı $a$ iki hissəyə bölmək: $a_1,a_2,\dots ,a_k$ və $a_{k+1},a_{k+2},\dots ,a_n$.

• Hər iki hissədən bir element silin.

$c$ birinci hissənin elementlərinin cəmi olsun və $d$ ikinci hissənin elementlərinin cəmi olsun. Sizə $|c-d|$-nin maksimum mümkün dəyərini tapmalısınız. Digər bir ifadə ilə, bu addımları yerinə yetirdikdən sonra əldə olunan hissələrin cəmlərinin fərqlərinin maksimum mümkün dəyərini tapmalısınız.

Boş hissənin elementlərinin cəmi $0$ olacağını götürə bilərsiniz.

Giriş verilənləri

Birinci sətirdə, $n$ $(2\le n\le 10^5)$ tam sayı — $a$ ardıcıllığında olan elementlərin sayıdır.

İkinci sətirdə, $n$ tam sayı — $a_i$ $(-10^3\le a_i\le 10^3)$ — ardıcıllığın elementləri.

Çıxış verilənləri

Birinci və yeganə sətirdə, bir tam sayı çıxış etməlisiniz — belə addımları yerinə yetirdikdən sonra əldə olunan hissələrin cəmlərinin fərqlərinin maksimum mümkün dəyərini.

Nümunələr

Qeyd

Birinci nümunədə, ardıcıllığı bölmək üçün tək bir yol $k=1$ seçməkdir, yəni iki altardıcıllıq $[1]$ və $[2]$ əldə etməkdir. Onlar hər ikisi də bir elementdən ibarətdir, belə ki, hər iki altardıcıllıqdan bir element silmək yeganə yol onları hər iki silməkdir. Beləliklə, altardıcıllıqlar boşalır, onların cəmləri $0$ olur, beləliklə cavab $|0-0|=0$-dır.

İkinci nümunədə, əməliyyatları yerinə yetirməyin $10$ yolu var:

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

2. $[2],[-5,4,-7]$ -> $[],[-5,-7]$ -> nəticə $|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$.

Görə biləcəyimiz kimi, burada maksimum mümkün dəyər $12$-dir, ki, bu dəyəri $k=2$ seçərək və birinci altardıcıllıqdan $-5$, ikinci altardıcıllıqdan isə $-7$ qalaraq əldə edə bilərik.

Üçüncü nümunədə, ardıcıllığı necə böldüyümüz və onlardan hansı elementi siləcəyimiz əsas deyil — əldə olunan hər hansı altardıcıllığın cəmi həmişə $0$ olacaq, beləliklə onların arasındakı fərq də həmişə $0$ olacaq.

Qiymətləndirmə

1. (4 bal): $n\le 3$;

2. (4 bal): massivin bütün elementləri bərabərdir ($a_i=a_j$ bütün $1\le i,j\le n$ üçün);

3. (5 bal): massivin bütün elementləri müsbət ədədlərdir ($a_i>0$ bütün $1\le i\le n$ üçün);

4. (7 bal): massiv artan sıra ilədir ($a_i\le a_j$ bütün $1\le i<j\le n$ üçün);

5. (10 bal): $n\le 300$;

6. (10 bal): $n\le 2000$;

7. (10 bal): əlavə məhdudiyyətlər yoxdur.