Algorithmen Übungen WS13/14

Eine Sekte will einen großen Tempel bauen, in dem kosmische Energie gespeichert werden soll. Der Tempel wird aus n quadratischen Räumen bestehen, die Seitenlängen s₁, s₂..., s_n haben. Der Boden jeden Raumes soll vollständig mit quadratischen Fliesen bedeckt werden, die alle die gleiche Größe haben sollen. Es herrscht der Glaube, dass die kosmische Energie am besten gespeichert werden kann, wenn die Fliesen möglichst groß sind.

Was ist die maximale Seitenlänge, die die Fliesen haben können? Die Größe der Fugen zwischen den Fliesen können Sie vernachlässigen.

Eingabe

Die erste Zeile der Eingabe enthält die Zahl n (2 ≤ n ≤ 50000). Die folgenden n Zeilen enthalten die Zahlen s₁, ..., s_n (1 ≤ s_i ≤ 10⁹).

Ausgabe

Geben Sie die maximale Seitenlänge der Fliesen aus, so dass die Böden aller Räume vollständig mit Fliesen dieser Größe bedeckt werden können, ohne dass sich Fliesen überlappen oder eine Fliese aufgeteilt wird.

Beispiel

Eingabe:
4
60
42
70
56
Ausgabe:
2