Rainfall Capture

Ήταν μια σκοτεινή και θυελλώδης νύχτα. Έβρεχε και έβρεχε και έβρεχε. Η Lucy θέλει να αιχμαλωτίσει μέρος της βροχής, αλλά έχει περιορισμένα υλικά. Έχει μια συλλογή από κολώνες, διαφόρων υψών, που μπορεί να διαμορφώσει για να αιχμαλωτίσει τη βροχή. Κάθε πυλώνας έχει ακέραιο αριθμό για ύψος και έχει μήκος και πλάτος ~1~. Μόλις η Lucy έχει τη διαμόρφωση των πυλώνων της, έχει αρκετό άλλο υλικό επένδυσης για να περικλείσει το μπροστινό και το πίσω μέρος για να επιτρέψει στη βροχή να γεμίσει όλο τον διαθέσιμο χώρο ανάμεσα σε στύλους. Η βροχή είναι υπεραρκετή και τυχόν υπερβολική βροχή θα ξεχειλίσει και θα απορροφηθεί από τη γη.

Για παράδειγμα, εάν η Lucy έχει κολώνες ύψους ~1~, ~5~, ~2~, ~1~, ~4~, θα μπορούσε να τις διαμορφώσει ως εξής (όλες οι διαμορφώσεις απεικονίζονται από το πλάι):

    *
    *  *
    *  *
    ** *
   *****

Που θα αιχμαλώτιζε ~5~ μονάδες βροχής (R) ως εξής:

    *
    *RR*
    *RR*
    **R*
   *****

Για αυτή την πρώτη συλλογή από κολώνες (~1~, ~5~, ~2~, ~1~, ~4~), θα μπορούσε επίσης να αιχμαλωτίσει ~6~ μονάδες βροχής ως εξής:

    *
    *RR*
    *RR*
   **RR*
   *****

Ως άλλο παράδειγμα, αν η συλλογή από κολώνες ήταν ~5~, ~1~, ~5~, ~1~, ~5~, η Lucy θα μπορούσε να αιχμαλωτίσει ~8~ μονάδες βροχής ως εξής:

    *R*R*
    *R*R*
    *R*R*
    *R*R*
    *****

Τέλος, η διαμόρφωση (~5, 1, 4, 1, 5~) αιχμαλωτίζει ~9~ μονάδες βροχής:

    *RRR*
    *R*R*
    *R*R*
    *R*R*
    *****

Η Lucy έχει ~N~ κολώνες (~2 \le N \le 500~) με ύψη ~H_1, h_2 ... h_N~ (~1 \le h_i \le 50~). Θα ήθελε να ξέρει, από όλες τις πιθανές διαμορφώσεις από κολώνες, ποιοί είναι όλοι οι εφικτοί όγκοι βροχόπτωσης που μπορεί να αιχμαλωτίσει χρησιμοποιώντας αυτές τις ~N~ κολώνες.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~N~ (~2 \le N \le 500~) που είναι ο αριθμός από κολώνες. Η επόμενη γραμμή περιέχει τους ακέραιους ~h_i~ (~1 \le h_i \le 50~, ~1 \le i \le N~), που αντιπροσωπεύουν το ύψος της ~i~-οστης κολώνας.

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 10~.

Για επιπλέον ~10~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 50~.

Έξοδος

Σε μία γραμμή, εκτυπώστε μια λίστα, χωρισμένη με κενά, από όλους τους εφικτούς ακέραιους όγκους βροχής που έχει αιχμαλωτιστεί, σε αύξουσα σειρά.

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

input

5
1 5 2 1 4

output

0 1 2 3 4 5 6 8

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

Αυτό είναι το πρώτο παράδειγμα που σας δόθηκε.

input

5
5 1 5 1 5

output

0 4 8

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

Αυτό είναι το δεύτερο παράδειγμα που σας δόθηκε.

input

5
5 1 4 1 5

output

0 1 3 4 5 6 7 8 9

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

Αυτό είναι το τρίτο παράδειγμα που σας δόθηκε.