Problem Description

Takahashi was given the following homework by his teacher to draw a line graph:

1. Given \( N \) non-negative integers \( A_1, A_2, \ldots, A_N \). However, it is guaranteed that \( A_1 = A_N = 0 \).
2. For \( i = 1, 2, \ldots, N \), place a point \( P_i \) at the coordinates \( (i, A_i) \) on a two-dimensional plane.
3. For \( i = 1, 2, \ldots, N-1 \), draw a line segment connecting point \( P_i \) and point \( P_{i+1} \).

Takahashi wants to finish his homework quickly, so he plans to secretly change the values of \( A_1, A_2, \ldots, A_N \) to reduce the total length of the drawn line segments.

However, to avoid being noticed by his teacher for changing the values secretly, if the changed values are \( B_1, B_2, \ldots, B_N \), they must satisfy all the following conditions:

• \( B_1, B_2, \ldots, B_N \) are all non-negative integers.
• The values of \( A_1 \) and \( A_N \) must not be changed. That is, \( B_1 = B_N = 0 \).
• \( \sum_{i=1}^{N} A_i = \sum_{i=1}^{N} B_i \)

When Takahashi changes the values of \( A_1, A_2, \ldots, A_N \) appropriately without being noticed by his teacher, find the minimum total length of the line segments he will draw.

Input Format

The input is given from the standard input in the following format:

\( N \) \( A_1 \) \( A_2 \) \( \ldots \) \( A_N \)

Output Format

Output the answer. The answer will be considered correct if the absolute or relative error is within \( 10^{-5} \).

Sample Input and Output

Sample Input #1

4
0 3 0 0

Sample Output #1

5.0644951022459797

Sample Input #2

7
0 1 2 3 4 5 0

Sample Output #2

10.3245553203367599

Notes/Hints

Constraints

• \( 2 \leq N \leq 100 \)
• \( 0 \leq A_i \leq 100 \)
• \( A_1 = A_N = 0 \)
• \( \sum_{i=1}^N A_i \leq 100 \)
• All inputs are integers.

Sample Explanation 1

Takahashi can minimize the total length of the line segments by changing \( A_2 \) to 1 and \( A_3 \) to 2.

见题面 Input 部分

见题面 Output 部分