Electronic Metronome

Time Limit : 1 sec, Memory Limit : 262144 KB

電子メトロノーム

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

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

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

Input

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

N
t_1
t_2
:
t_N

1行目に、メトロノームの数N (1 ≤ N ≤ 105)が与えられる。続くN行に、各メトロノームにあらかじめ設定された間隔t_i (1 ≤ t_i ≤ 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 秒ごとにすべてのメトロノームの音が同時に鳴り、これが最小の周期である。


Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-11-3
http://web-ext.u-aizu.ac.jp/pc-concours/