Problem C
Folgen

Eine Folge positiver ganzer Zahlen $(x_1,\dots ,x_m)$ ist gut, wenn $x_1=1$ und für jedes $1<j\le m$ entweder $x_j=x_{j-1}+1$ oder $x_j=x_k\cdot x_l$ für ein $k$ und $l$ mit $0<k\le l<j$ gilt. Zum Beispiel sind die Folgen $(1,1)$ und $(1,2)$ beide gut, aber die Folge $(1,3)$ ist nicht gut. Für $n$ gegebene ganze Zahlen $w_1,\dots ,w_n$ definieren wir das Gewicht einer ganzzahligen Folge $(x_1,\dots ,x_m)$, die $1\le x_j\le n$ für jedes $1\le j\le m$ erfüllt, als

Sei zum Beispiel $w_1=10,w_2=42,w_3=1$. Dann hat die Folge $(1,1)$ das Gewicht $20$ und die Folge $(1,3)$ das Gewicht $11$. Für $1\le v\le n$ definiere $s_v$ als das kleinstmögliche Gewicht einer guten Folge, die den Wert $v$ enthält.

Deine Aufgabe ist es, die Werte $s_1,\dots ,s_n$ zu bestimmen.

Eingabe

Die erste Zeile der Eingabe besteht aus der ganzen Zahl $n$, der Anzahl der Gewichte. Die nächsten $n$ Zeilen enthalten die ganzzahligen Gewichte $w_1,\dots ,w_n$.

Ausgabe

Gib $n$ Zeilen aus, die der Reihe nach $s_1$, $\dots$, $s_n$ enthalten.

Beschränkungen und Bewertung

Es gilt immer $1\le n\le 30000$ und $1\le w_i\le {10}^6$ für jedes $1\le i\le n$.

Deine Lösung wird an einer Reihe von Testgruppen getestet, von denen jede eine bestimmte Anzahl von Punkten wert ist. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine Testgruppe zu erhalten, musst du alle Testfälle in der Testgruppe lösen. Deine endgültige Punktzahl ist die maximale Punktzahl für eine einzelne Einsendung.

3
10
42
1

10
52
53