Zərif şəkildə yenidən düzülmüş məbləğ

Verilmiş ardıcıllıq $n$ tam ədədlərdən $\{a_1,a_2,...,a_n\}$ ibarətdir. Elə bir çevrilmə tapmaq lazımdır ki, qonşu elementlərin fərqlərinin modullarının cəmi maksimum olsun. Bu ən böyük cəmi zərif adlandıracağıq.

Məsələn, $\{4,2,1,5\}$ ardıcıllığını nəzərdən keçirək. Axtarılan çevrilmə $\{2,5,1,4\}$ olacaq və onun zərif cəmi $|2–5|+|5–1|+|1–4|=3+4+3=10$-a bərabərdir. Digər $24$ çevrilmələr üçün zərif cəmin dəyəri $10$-dan böyük deyil.

Giriş verilənləri

Birinci sətir testlərin sayını $t(t<100)$ ehtiva edir. Hər bir növbəti sətir ayrı bir testdir. Hər bir giriş sətiri $n(1<n<51)$ ədədi ilə başlayır, sonra isə $n$ qeyri-mənfi ədədlərdən ibarət ardıcıllıq gəlir. Ardıcıllıqda hər bir ədəd $1000$-dən çox deyil.

Çıxış verilənləri

Hər bir test üçün onun nömrəsini və zərif cəmin dəyərini çıxarın.

Nümunələr