Problem description


Odwracanie Znaków
(C)
Limit pamięci: 128 MB
Limit czasu: 2.00 s

W laboratorium zapisano ciąg liczb całkowitych. Jedyna dostępna operacja pozwala jednocześnie odwrócić znaki dwóch sąsiednich liczb.

Dla tablicy A składającej się z N elementów możesz dowolną liczbę razy (być może zero razy) wykonać następującą operację:

  • wybierz indeks i spełniający 1 ≤ i < N,
  • zastąp Ai przez  − Ai oraz Ai + 1 przez  − Ai + 1.

Do rozwiązania jest T niezależnych zestawów testowych. Dla każdego z nich wyznacz największą możliwą sumę wszystkich elementów tablicy po wykonaniu wybranych operacji.

Wejście

W pierwszym wierszu znajduje się liczba całkowita T - liczba zestawów testowych.

Opis każdego zestawu testowego składa się z dwóch wierszy. W pierwszym z nich znajduje się liczba całkowita N - długość tablicy.

W drugim wierszu znajduje się N liczb całkowitych A1, A2, …, AN - początkowe wartości elementów tablicy.

Wyjście

Dla każdego zestawu testowego wypisz w osobnym wierszu jedną liczbę całkowitą - największą sumę elementów tablicy, jaką można uzyskać.

Ograniczenia

1 ≤ T ≤ 1000, 2 ≤ N ≤ 200 000,  − 109 ≤ Ai ≤ 109, suma wartości N we wszystkich zestawach testowych nie przekracza 200 000

Przykład

Wejście Wyjście Wyjaśnienie
5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1
1
13
6
39
2

Wyjaśnijmy pierwszy i drugi zestaw. W pierwszym wybieramy pierwszą parę (−1,−1) i zmieniamy znaki obu liczb. Tablica zmienia się z [−1,−1,−1] na [1,1,−1], a suma jej elementów wynosi 1 + 1 − 1 = 1. W drugim zestawie wybieramy sąsiednie elementy  − 5 i 0. Po zmianie ich znaków otrzymujemy tablicę [1,5,5,0,2], której suma wynosi 1 + 5 + 5 + 0 + 2 = 13.

Wejście Wyjście Wyjaśnienie
6
2
-5 2
4
-2 -2 3 3
4
0 -7 -8 -9
5
-4 1 1 1 1
2
-1 0
3
1000000000 1000000000 1000000000
3
10
24
6
1
3000000000

Wyjaśnijmy pierwszy i drugi zestaw. W pierwszym jedyną parę (−5,2) zmieniamy na (5,−2). Otrzymana suma to 5 − 2 = 3. W drugim zestawie wybieramy pierwszą parę (−2,−2) i zmieniamy znaki obu elementów. Powstaje tablica [2,2,3,3], a suma jej elementów wynosi 2 + 2 + 3 + 3 = 10.