Cokolade

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \leq N \leq 100)~.

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

Οι αριθμοί είναι από το διάστημα ~[1,\;10^8]~.

Έξοδος

Τυπώστε ~N~ γραμμές, με κάθε γραμμή να περιέχει έναν μόνο ακέραιο αριθμό.

Η ~s~-οστή γραμμή θα πρέπει να περιέχει τον απαιτούμενο αριθμό για μια ομάδα μεγέθους ~s~ ή -1 εάν δεν θα υπάρξει ποτέ ομάδα αυτού του μεγέθους.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~30~% των συνολικών πόντων, ο αριθμός των γλυκών σε όλα τα τραπέζια δεν θα υπερβαίνει το ~10^3~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον ~30~% των συνολικών πόντων, ο αριθμός των γλυκών σε όλα τα τραπέζια δεν θα υπερβαίνει το ~10^6~.

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

input

5
11 10 9 6 4

output

1
2
3
6
12

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

Την πρώτη μέρα, κάθε τραπέζι θα κοινωνικοποιηθεί μόνο με τον εαυτό του, επομένως η απάντηση για τις ομάδες μεγέθους 1 είναι 1. Ήδη τη δεύτερη μέρα, τα άτομα που κάθονται στα τραπέζια 1 και 2 θα πάρουν 5 καραμέλες κατά κεφαλήν και θα κοινωνικοποιηθούν μαζί, οπότε η απάντηση για μια ομάδα μεγέθους 2 είναι 2.
Την τρίτη μέρα, τα τραπέζια 1, 2 και 3 θα κοινωνικοποιηθούν (γιατί όλοι έχουν 3 καραμέλες κατά κεφαλήν).
Την έκτη μέρα, τα τραπέζια 1, 2, 3 και 4 θα κοινωνικοποιηθούν (γιατί πλέον έχουν 1 καραμέλα κατά κεφαλήν).
Τέλος, τη δωδέκατη μέρα, όλα τα τραπέζια θα κοινωνικοποιηθούν μαζί γιατί θα πάρουν όλα μηδέν καραμέλες κατά κεφαλήν.

input

3
5 5 5

output

-1
-1
1

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

Όλα τα τραπέζια έχουν την ίδια ποσότητα καραμέλας κατά κεφαλήν, επομένως μια ομάδα μεγέθους μικρότερη από 3 δεν θα υπάρξει ποτέ.

input

8
12 16 95 96 138 56 205 84

output

1
5
14
49
96
97
139
206