004 - 電子メトロノーム

時間制限 1 秒 / メモリ制限 256 MB / 得点 6 / x 3 /


TLE
1sec
MLE
256MB
得点
6

PCK 君はN 台の電子メトロノームで遊んでいる。i 番目のメトロノームはti 秒間隔で音が一瞬だけ鳴るようにあらかじめ設定されている。PCK 君はすべてのメトロノームを同時に起動した。

PCK 君は、音が鳴る間隔がバラバラでも、すべてのメトロノームの音が同時に鳴る瞬間が一定の周期で訪れることに気が付いた。この現象をもっと楽しむために、 PCK 君はいくつかのメトロノームの鳴る間隔を調整することで、すべてのメトロノームの音が同時に鳴る周期を短くしようとしている。ただし、メトロノームの音が 鳴る間隔は増やすことしかできない。

メトロノームの数とそれぞれにあらかじめ設定された秒単位の間隔ti を入力とし、i 番目のメトロノームの音が鳴る間隔をある負でない整数di だけ増やすことで、全てのメトロノームの音が同時に鳴る周期を最も短くしたときの、di の合計の最小値を求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N
t1
t2
:
tN

1行目に、メトロノームの数N (1 ≤ N ≤ 105)が与えられる。続くN行に、各メトロノームにあらかじめ設定された間隔ti (1 ≤ ti ≤ 104)が整数で与えられる。

Output

最小値を1行に出力する。

Sample Input 1

3
3
6
8

Sample Output 1

3

間隔がそれぞれ3, 6, 8 のメトロノームを一斉に起動すると、24 秒ごとにすべてのメトロノームの音が同時に鳴る。1 つ目のメトロノームの間隔を1 秒、2 つ目の間隔を2 秒長くすると、その周期は最も短い8 秒となる。

Sample Input 2

2
10
10

Sample Output 2

0

間隔が10,10 のメトロノームを同時に起動すると、10 秒ごとにすべてのメトロノームの音が同時に鳴り、これが最小の周期である。