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

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

The fairness of the match is measured by the absolute difference between the sum of strengths of the students in team ~A~ and team ~B~, 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 ~l~ in step ~1~. Please help them out!

Constraints

~2 \le N \le 10^6~

~1 \le s_i \le 10^9~

Subtask 1 [10%]

~N = 2~

Subtask 2 [20%]

~2 \le N \le 2 \times 10^3~

Subtask 3 [70%]

No additional constraints.

Input Specification

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

The second line contains ~N~ space-separated integers ~s_1, s_2, \dots, s_N~, the strengths of the students.

Output Specification

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

Sample Input

5
1 4 6 3 7

Sample Output

1 1 3 1 3

Explanation

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

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

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

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

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