AlgoLiga 2018

Znajdź największą sumę podciągu w ciągu liczb całkowitych o następujących własnościach:

• musi być spójny
• jeśli będziemy przechodzić po wyrazach od lewej srony do prawej to suma napotkanych do danego momentu liczb nieparzystych musi być zawsze nie mniejsza niż suma napotkanych do tego momentu liczb parzystych
• to samo dotyczy przejścia z prawej do lewej strony tego samego podciągu
• szukany podciąg musi zaczynać się i kończyć liczbą nieparzystą
• dopóki nie napotkamy liczby parzystej, to każda nieparzysta dodatnia, ujemna, czy też ich suma, będzie zawsze większa od nieokreślonej do tej pory sumy liczb parzystych

Wejście

W pierwszym wierszu liczba określająca liczbę zestawów danych (nie więcej niż 1000).

Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu jedna liczba określająca długość ciągu (nie wiecej niż 100 000). W drugim wierszu kolejne liczby ciągu będące liczbami całkowitymi, gdzie każda z nich mieści się w przedziale [-10⁶... 10⁶]. 

Wyjście

Dla każdego zestawu jedna liczba określająca największą taką sumę. Gdy w ciągu nie ma liczb nieparzystych to wypisujemy 0.

Przykład

Wejście:
3
5
1 3 4 6 3
7
2 5 4 5 3 4 5
15
-3 -3 5 5 4 0 3 -4 -1 -2 2 -3 4 -3 -1
Wyjście:
4
26
12