$n \ge 3$인 음이 아닌 정수 배열 $s_1, \dots, s_n$이 주어졌을 때, $n$개의 음이 아닌 실수(반드시 정수일 필요는 없음) 수열 $x_1, x_2, \dots, x_n$이 모든 $i$에 대하여 $x_i + x_{i+1} \le s_i$를 만족하면 이를 균형 잡힌(balanced) 수열이라고 부릅니다. 여기서 $x_{n+1} = x_1$입니다.

$f(s_1, s_2, \dots, s_n)$을 모든 균형 잡힌 가중치 구성 중 $x_1 + x_2 + \dots + x_n$의 최댓값이라고 정의합니다.

음이 아닌 정수 배열 $a_1, a_2, \dots, a_n$이 주어집니다.

$n - 2$개의 수 $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$을 구하세요.

입력

첫 번째 줄에는 정수 $n$ ($3 \le n \le 100\,000$)이 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$)이 주어집니다.

출력

$n - 2$개의 수 $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$을 출력하세요.

모든 값에 대하여 상대 오차 또는 절대 오차가 $10^{-9}$ 이하이면 정답으로 간주됩니다.

예제

입력 1

4
20 20 20 15

출력 1

30.0 35

참고

첫 번째 예제에서, 세 개의 원소를 가진 접두사에 대해서는 $\{10, 10, 10\}$으로 값을 설정할 수 있고, 다음 접두사에 대해서는 $\{10.1, 9.9, 10.1, 4.9\}$로 값을 설정할 수 있습니다.

입력 2

6
1 2 1 2 1 2

출력 2

2 2 3 3

입력 3

12
1 1 1 3 1 1 2 5 3 2 1 2

출력 3

1.5 2 3 3 4 5 8 8 9 9