PCK 君はN 台の電子メトロノームで遊んでいる。i 番目のメトロノームはt_i 秒間隔で音が一瞬だけ鳴るようにあらかじめ設定されている。PCK 君はすべてのメトロノームを同時に起動した。
PCK 君は、音が鳴る間隔がバラバラでも、すべてのメトロノームの音が同時に鳴る瞬間が一定の周期で訪れることに気が付いた。この現象をもっと楽しむために、PCK 君はいくつかのメトロノームの鳴る間隔を調整することで、すべてのメトロノームの音が同時に鳴る周期を短くしようとしている。ただし、メトロノームの音が鳴る間隔は増やすことしかできない。
メトロノームの数とそれぞれにあらかじめ設定された秒単位の間隔t_i を入力とし、i 番目のメトロノームの音が鳴る間隔をある負でない整数d_i だけ増やすことで、全てのメトロノームの音が同時に鳴る周期を最も短くしたときの、d_i の合計の最小値を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
N t_1 t_2 : t_N
１行目に、メトロノームの数N (1 ≤ N ≤ 105)が与えられる。続くN行に、各メトロノームにあらかじめ設定された間隔t_i (1 ≤ t_i ≤ 104)が整数で与えられる。
最小値を１行に出力する。
3 3 6 8
3
間隔がそれぞれ3, 6, 8 のメトロノームを一斉に起動すると、24 秒ごとにすべてのメトロノームの音が同時に鳴る。1 つ目のメトロノームの間隔を1 秒、2 つ目の間隔を2 秒長くすると、その周期は最も短い8 秒となる。
2 10 10
0
間隔が10,10 のメトロノームを同時に起動すると、10 秒ごとにすべてのメトロノームの音が同時に鳴り、これが最小の周期である。