Mô tả và yêu cầu

Xét trò chơi như sau: Máy tính t ạo ngẫu nhiên một dãy số nguyên không âm
𝑎1,𝑎2, … ,𝑎𝑛. Số 𝑎1 có 1 số liền kề với 𝑎2, số 𝑎𝑛 có 1 số liền kề với 𝑎𝑛−1, các số
khác có hai số liền kề. Người chơi sẽ được tổng điểm thưởng khi thực hiện liên tiếp
một trong các hành động chọn số dưới đây:
1. Chọn một số có 2 số liền kề, điểm thưởng là trung bình cộng của hai số liền
kề, sau hành động này số được chọn bị xóa.
2. Chọn một số có 1 số liền kề (có thể do các lượt chọn trước đã xóa số kề hoặc
do số nằm ở vị trí 1 ho ặc vị trí cuối), điểm thưởng là số liền kề, sau hành động
này số được chọn bị xóa.
3. Chọn một số không có số liền kề, khi đó sẽ không được điểm thưởng nào,
sau hành động này số được chọn bị xóa.
Yêu cầu: Hãy tìm cách chọn số để tổng điểm thưởng là lớn nhất.
Dữ fiệu: Vào từ thiết bị nhập chuẩn gồm:
Dòng đầu tiên c hứa số nguyên dương 𝑇 là số bộ dữ liệu. Tiếp theo là 𝑇 nhóm
dòng, mỗi nhóm có định dạng như sau:
 Dòng đầu của nhóm chứa số nguyên duy nhất 𝑛.
 Dòng thứ hai của nhóm chứa 𝑛 số nguyên không âm 𝑎1, 𝑎2, … ,𝑎𝑛(𝑎𝑖 ≤ 109,
∀𝑖 = 1 → 𝑛 ) mô tả dãy số ban đầu.
Kết quả: Ghi ra thiết bị xuất chuẩn gồm 𝑇 dòng, mỗi dòng chứa một số thực (với
độ chính xác một chữ số sau dấu phẩy) là tổng điểm lớn nhất đạt được tương ứng
với từng bộ dữ liệu.

Ví dụ

INPUT                                OUTPUT
          2                                       5.0
          3                                       5.0
          1 2 3
          4
          2 0 1 4

Ràng buộc:

      Subtask 1:   40% số test có 𝑛     ≤  8
      Subtask 2: 30% số test có 𝑛       ≤  100
      Subtask 3: 30% số test có 𝑛       ≤  106