It's finally sports day at Nanashi high school! There are students numbered from to initially huddled up in a circle, with student to the left of student for all , and student to the left of student . They've decided to play a game of the classic tug of war, and it is known that student has a strength of . To make teams, they will follow the following procedure:

- Choose an integer from to . Form a line where student stands at the far left, and the student originally to the left of student is now at the far right. The relative positions of all other students remain the same.
- Choose a splitting point between any two students. All students to the left of the splitting point are assigned team , and all students to the right are assigned team .

The fairness of the match is measured by the absolute difference between the sum of strengths of the students in team and team , with the fairest game occurring when the difference is minimum. Since the students would like the fairest game possible, they would like to know the fairest possible match for all choices of in step . Please help them out!

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No additional constraints.

#### Input Specification

The first line contains an integer , the number of students.

The second line contains space-separated integers , the strengths of the students.

#### Output Specification

Output space-separated integers, the -th integer being the minimum possible difference between the sum of strengths of the students in team and team if is chosen in the first step.

#### Sample Input

```
5
1 4 6 3 7
```

#### Sample Output

`1 1 3 1 3`

#### Explanation

If is chosen in the first step, the list of the strengths of the students from left to right is . It is optimal to choose a splitting point between the students with strengths and for a difference in total strengths of .

If is chosen in the first step, the list of the strengths of the students from left to right is . It is optimal to choose a splitting point between the students with strengths and for a difference in total strengths of .

If is chosen in the first step, the list of the strengths of the students from left to right is . It is optimal to choose a splitting point between the students with strengths and for a difference in total strengths of .

## Comments