카드 모두 잇기

다니엘은 사탕 한 봉지와 카드 $N$장을 가지고 있다. 카드마다 양의 정수 $P_i$가 하나씩 적혀 있다.

사탕을 먹던 다니엘은 놀이를 하나 떠올렸다. 적힌 수가 $a$와 $b$인 카드 두 장을 끈으로 묶을 수 있고, 한 번 묶을 때마다 사탕을 $\min(a \bmod b,\ b \bmod a)$개 먹어야 한다. $x \bmod y$는 $x$를 $y$로 나눈 나머지이다.

다니엘은 카드 한 장을 집어 올리면 나머지 카드가 모두 딸려 올라오도록 카드를 묶으려고 한다. 카드 한 장은 다른 카드 몇 장과도 직접 묶을 수 있다. 몸매를 신경 쓰는 다니엘은 사탕을 많이 먹고 싶지 않다.

모든 카드가 하나로 이어지도록 묶을 때 먹어야 하는 사탕 개수의 최솟값을 구하라.

첫째 줄에 양의 정수 $N$이 주어진다. ($1 \le N \le 10^5$)

다음 $N$개의 줄에 카드에 적힌 양의 정수 $P_i$가 한 줄에 하나씩 주어진다. ($1 \le P_i \le 10^7$)

모든 카드를 하나로 잇기 위해 먹어야 하는 사탕 개수의 최솟값을 첫째 줄에 출력한다.

첫 번째 예제에서 다니엘은 첫째 카드와 둘째 카드를 묶어 사탕을 0개 먹고, 둘째 카드와 셋째 카드를 묶어 0개를 먹고, 첫째 카드와 넷째 카드를 묶어 1개를 먹는다. 이렇게 하면 사탕 1개로 카드 네 장이 모두 이어진다.