카드 합치기

Panko는 한 줄로 놓인 N장의 카드로 게임을 한다. i번째 카드에는 정수 Ai가 적혀 있다.

게임은 N - 1라운드에 걸쳐 진행된다. 각 라운드에서 Panko는 인접한 두 카드를 골라 합친다. 두 카드에 적힌 정수를 X, Y라 하자. 두 카드를 합치면 Panko는 X + Y가 적힌 새 카드를 만든다. 그런 다음 원래 두 카드를 줄에서 빼고 그 자리에 새 카드를 놓는다. 마지막으로 Panko는 합친 대가로 X + Y점을 받는다. 각 라운드에서 Panko는 현재 존재하는 모든 인접한 카드 쌍 중에서 하나를 균등한 확률로 고른다.

N - 1라운드가 모두 끝난 뒤 Panko의 총점은 각 합치기에서 받은 점수의 합이다. 게임이 끝났을 때 Panko의 총점의 기댓값은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 다음 줄에는 N개의 정수가 주어지며, 카드의 초기 배치를 나타낸다. i번째 정수는 Ai이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 게임이 끝났을 때의 기대 총점이다.

y는 정답과의 절대 오차 또는 상대 오차가 10-6 이내이면 정답으로 인정된다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 1 ≤ Ai ≤ 109.

예제 1에서 N = 3이다. 카드의 초기 배치는 [2, 1, 10]이다. 첫 라운드에서 Panko는 두 가지 선택지가 있고, 그중 하나를 무작위로 고른다.

• Panko가 첫 번째 쌍(2, 1)을 합치면 카드 줄은 [3, 10]이 되고, 총점에 2 + 1 = 3점이 더해진다. 두 번째 라운드에는 남은 쌍이 하나뿐이다(3, 10). 이것을 합치면 카드 줄은 [13]이 되고, 총점에 3 + 10 = 13점이 더해진다. Panko는 3 + 13 = 16점으로 게임을 마친다.
• Panko가 두 번째 쌍(1, 10)을 합치면 카드 줄은 [2, 11]이 되고, 총점에 1 + 10 = 11점이 더해진다. 두 번째 라운드에는 남은 쌍이 하나뿐이다(2, 11). 이것을 합치면 카드 줄은 [13]이 되고, 총점에 2 + 11 = 13점이 더해진다. Panko는 11 + 13 = 24점으로 게임을 마친다.

따라서 Panko가 게임을 마쳤을 때의 기대 점수는 (16 + 24)/2 = 20이다.

예제 2에서 N = 5이다. 카드의 초기 배치는 [19, 3, 78, 2, 31]이다. 가능한 경우가 너무 많아 여기에 모두 나열할 수 없으므로 한 가지 가능한 게임만 살펴본다.

• 첫 라운드에서 Panko가 쌍(78, 2)을 합치면 카드 줄은 [19, 3, 80, 31]이 되고, 점수에 78 + 2 = 80이 더해진다.
• 두 번째 라운드에서 Panko가 쌍(80, 31)을 합치면 카드 줄은 [19, 3, 111]이 되고, 점수에 80 + 31 = 111이 더해진다.
• 세 번째 라운드에서 Panko가 쌍(19, 3)을 합치면 카드 줄은 [22, 111]이 되고, 점수에 19 + 3 = 22가 더해진다.
• 네 번째 라운드에서 Panko가 쌍(22, 111)을 합치면 카드 줄은 [133]이 되고, 점수에 22 + 111 = 133이 더해진다.

위에서 설명한 게임이 끝났을 때 Panko의 총점은 80 + 111 + 22 + 133 = 346이다.