Symmetric Mountains

Η Ρεμπέκα είναι ξεναγός και προσπαθεί να διαφημίσει τα Βραχώδη Όρη για το περιοδικό της. Πρόσφατα τράβηξε μια πολύ όμορφη φωτογραφία που περιέχει ~N~ βουνά, όπου το ~i~-οστό βουνό από αριστερά έχει ύψος ~h_{i}~. Θα περικόψει αυτή τη φωτογραφία για το περιοδικό της, αφαιρώντας ενδεχομένως κάποια βουνά από την αριστερή πλευρά της εικόνας και αφαιρώντας ενδεχομένως και κάποια βουνά από τη δεξιά πλευρά της εικόνας. Δηλαδή, μια περικοπή θα περιέχει διαδοχικά βουνά ξεκινώντας από το ~l~-οστό προς το ~r~-οστό βουνό όπου ~l \le r~. Για να αφήσει ικανοποιημένους τους αναγνώστες του περιοδικού της, η Ρεμπέκα θα προσπαθήσει να βρει την πιο συμμετρική περικοπή.

Θα μετράμε την τιμή ασυμμετρίας μιας περικοπής ως το άθροισμα της απόλυτης διαφοράς για κάθε ζεύγος βουνών που ισαπέχουν από το μέσο της περικοπής. Για να βοηθηθείτε στην κατανόηση αυτού του ορισμού, σημειώστε ότι η απόλυτη τιμή ενός αριθμού ~v~, που γράφεται ως ~|v|~, είναι η μη αρνητική τιμή του ~v~: για παράδειγμα ~|-6| = 6~ και ~|14| = 14~. Η τιμή ασυμμετρίας μιας περικοπής είναι το άθροισμα όλων των ~|h_{l+i} - h_{r-i}|~ για ~0 \le i \le \frac{r-l}{2}~. Για να διατυπώσουμε αυτόν τον τύπο με διαφορετικό τρόπο, αντιστοιχίζουμε τα βουνά σε ζεύγη, δουλεύοντας από έξω προς το κέντρο, υπολογίζουμε την απόλυτη διαφορά υψών για κάθε ένα από αυτά τα ζεύγη και τα αθροίζουμε.

Επειδή η Ρεμπέκα δεν γνωρίζει πόσο φαρδιά πρέπει να είναι η εικόνα, για όλα τα πιθανά μήκη περικοπής, βρείτε την τιμή ασυμμετρίας της πιο συμμετρικής περικοπής (την περικοπή με την ελάχιστη τιμή ασυμμετρίας).

Είσοδος

Η πρώτη γραμμή θα αποτελείται από έναν ακέραιο αριθμό ~N~, που θα αντιπροσωπεύει τον αριθμό των βουνών στην εικόνα. Η δεύτερη γραμμή θα αποτελείται από ~N~ ακέραιους αριθμούς χωρισμένους με κενό διάστημα, όπου ο ~i~-οστός ακέραιος από αριστερά αντιπροσωπεύει το ύψος ~h_{i}~.

Για ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 300~, ~0 \le h_{i} \le 10^{5}~.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 5000~, ~0 \le h_{i} \le 10^{5}~ και η τα ύψη των βουνών βρίσκονται σε μια μη φθίνουσα σειρά από αριστερά προς τα δεξιά.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 5000~, ~0 \le h_{i} \le 10^{5}~.

Έξοδος

Εξάγετε σε μία γραμμή ~N~ ακέραιους αριθμούς χωρισμένους με κενά διαστήματα, όπου ο ~i~-οστός ακέραιος από αριστερά θα είναι η τιμή ασυμμετρίας της πιο συμμετρικής εικόνας περικοπών μήκους ~i~.

Παραδείγματα

input

7
3 1 4 1 5 9 2

output

0 2 0 5 2 10 10

Επεξήγηση του πρώτου παραδείγματος:

Θα δείξουμε γιατί η πέμπτη τιμή από αριστερά είναι ~2~. Ας προσπαθήσουμε να υπολογίσουμε όλες τις τιμές ασυμμετρίας των περικοπών μήκους ~5~.

Το ύψος των βουνών στην πρώτη περικοπή είναι ~[3, 1, 4, 1, 5]~. Η τιμή ασυμμετρίας αυτής της περικοπής είναι ~|3 - 5| + |1 - 1| + |4 - 4| = 2~.

Το ύψος των βουνών στη δεύτερη περικοπή είναι ~[1, 4, 1, 5, 9]~. Η τιμή ασυμμετρίας αυτής της περικοπής είναι ~|1 - 9| + |4 - 5| + |1 - 1| = 9~.

Το ύψος των βουνών στην τελευταία περικοπή είναι ~[4, 1, 5, 9, 2]~. Η τιμή ασυμμετρίας αυτής της περικοπής είναι ~|4 - 2| + |1 - 9| + |5 - 5| = 10~.

Επομένως, η πιο συμμετρική περικοπή μήκους ~5~ είναι ~2~.

input

4
1 3 5 6

output

0 1 3 7

Επεξήγηση του δεύτερου παραδείγματος:

Το δείγμα αυτό ικανοποιεί το δεύτερο υποερώτημα. Σημειώστε ότι η μόνη περικοπή μήκους ~4~ είναι η ~[1, 3, 5, 6]~ η οποία έχει τιμή ασυμμετρίας ~|1 - 6| + |3 - 5| = 7~.