산울타리 다듬기 (Large)

코헨 남작의 정원에는 산울타리가 있다. 산울타리는 일직선으로 나란히 심은 관목 $N$개로 이루어지고, 관목에는 왼쪽에서 오른쪽으로 1번부터 $N$번까지 번호가 붙어 있다. $i$번 관목의 높이는 정수다. 이웃 사람들은 모든 관목의 높이가 같아지도록 산울타리를 다듬지만, 남작의 정원사는 다른 규칙을 따른다.

규칙은 이렇다. 정원사는 2번 관목에서 출발해 오른쪽으로 이동하면서 $2, 3, \dots, N-1$번 관목을 이 순서대로 살펴본다. $i$번 관목 앞에 서면 $i-1$번 관목과 $i+1$번 관목의 현재 높이의 평균을 구한다. $i$번 관목이 그 평균보다 높으면 윗부분을 잘라 높이를 평균과 정확히 같게 맞춘다. 평균과 같거나 평균보다 낮으면 그 관목은 그대로 두고 오른쪽 관목으로 넘어간다. 정원사는 한 번 지나간 관목으로 되돌아오지 않으므로, $i$번 관목의 평균을 구할 때 쓰는 $i-1$번 관목의 높이는 이미 다듬은 뒤의 높이다.

정원사가 작업을 끝낸 뒤 $N-1$번 관목의 높이를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어진다. 첫째 줄에는 정수 $N$이 주어지고, 둘째 줄에는 1번 관목부터 $N$번 관목까지의 높이를 나타내는 정수 $N$개가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $3 \le N \le 1000$
• 각 높이는 1 이상 1000 이하의 정수다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 정원사가 작업을 끝낸 뒤의 $N-1$번 관목 높이다. $y$는 소수점 아래 여섯째 자리까지 출력하며, 소수점 아래 여섯째 자리로 나타낼 수 있는 값 중 가장 가까운 값으로 반올림한다. 정답이 그런 두 값의 정확히 중간에 놓이는 입력은 주어지지 않는다.