Tổng lớn nhất trên vị trí chẵn

Cho một mảng $a$ gồm $n$ số nguyên. Các chỉ số của mảng được đánh số từ $0$ (phần tử đầu tiên là $a_0$, phần tử thứ hai là $a_1$, ...).

Bạn được phép đảo ngược nhiều nhất một đoạn con liên tiếp của mảng. Đoạn con $a[l;r]$ là dãy $a_l,a_{l+1},\dots ,a_r$; đảo ngược nó biến dãy này thành $a_r,a_{r-1},\dots ,a_l$.

Hãy chọn đoạn con để đảo ngược (hoặc không đảo ngược gì cả) sao cho tổng các phần tử ở những vị trí chẵn của mảng kết quả là lớn nhất, tức là tổng $a_0+a_2+a_4+\cdots$ đạt giá trị lớn nhất có thể.

Có $t$ bộ dữ liệu độc lập cần trả lời.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu. Sau đó là $t$ bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ là độ dài mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng riêng tổng lớn nhất của các phần tử ở vị trí chẵn sau khi đảo ngược nhiều nhất một đoạn con.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ