Info Winter Speed Code 2023 - Clasele XI-XII | noconsec

Cerință

Se dă un șir de $n$ numere. Să se aleagă valori din șir astfel încât nu alegem două valori pe poziții consecutive, iar suma lor este maximă.

Date de intrare

Pe prima linie se va afla $t$, numărul de teste.

Fiecare dintre cele $t$ teste va fi descris după cum urmează:

Pe prima linie vom avea $n$, reprezentând numărul de numere din șir.

Pe cea de-a doua linie vom avea valorile vectorului $v$.

Date de ieșire

Se vor afișa $t$ numere, câte unul corespunzător fiecăruia dintre cele $n$ teste.

Restricții și precizări

• $1 \leq t \leq 10$
• $1 \leq n \leq 10^5$
• $1 \leq v_i \leq 10^6$

Exemplu

stdin

3
7
5 4 1 4 3 8 5
5
9 8 7 9 8
6
11 9 0 13 14 15

stdout

17
24
39