Problem description
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 |
|
|
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 |
|
|
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. |