Xét trò chơi trên dãy số như sau: Máy tính tạo ngẫu nhiên một dãy số nguyên không âm \(a_1, a_2, \dots, a_n\). Số \(a_1\) có một số liền kề là số \(a_2\), số \(a_n\) có một số liền kề là số \(a_{n-1}\), các số khác có hai số liền kề. Bạn được phép thực hiện liên tiếp một trong các hành động chọn số dưới đây để tổng điểm thưởng là lớn nhất:

1. Chọn một số có hai 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ó một 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í \(n\) ban đầu), đ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ề, bạn 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.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu. Tiếp theo là \(T\) nhóm dòng, mỗi nhóm có định dạng sau:
  • Dòng đầu của nhóm chứa số nguyên \(n\);
  • Dòng thứ hai của nhóm chứa \(n\) số nguyên không âm mô tả dãy số ban đầu.

Output

• Gồm \(T\) 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 chấm) là tổng điểm lớn nhất đạt được tương ứng với từng bộ dữ liệu.

Constraints

• Tổng các số \(n\) không vượt quá \(10^6\).
• Các số trong dãy không vượt quá \(10^9\).
• Subtask \(1\) (\(20\%\) số điểm): \(n \le 8\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\);
• Subtask \(3\) (\(60\%\) số điểm): \(n \le 10^6\);

Example

2
3
1 2 3
4 
2 0 1 4

5.0
5.5

Nguồn: 3D'21