Per đang có ~1~ gói kẹo và ~n~ lá bài. Mỗi lá bài được ghi số ~p_i~ trên đó. Trong lúc ăn kẹo, Per nghĩ ra một bài toán thú vị như sau:

Dùng dây nối hai lá ~i, j~ thì sẽ ăn ~\min(X, Y)~ cái kẹo, trong đó ~X = p_i \mod p_j~, ~Y = p_j \mod p_i~.

Per muốn nối các lá bài lại sao cho tất cả các lá đều được kết nối với nhau.

Per sợ sâu răng nên muốn ăn ít kẹo nhất có thể mà vẫn có thể kết nối ~n~ lá với nhau được. Các bạn hãy thử tìm cách giúp Per nhé!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~) — số lượng lá bài.

Dòng tiếp theo chứa ~n~ số nguyên ~p_i~ (~1 \le p_i \le 10^7~) — giá trị lá bài thứ ~i~.

Kết quả

In ra một số nguyên duy nhất — số kẹo tối thiểu Per phải ăn để có thể kết nối ~n~ lá bài với nhau.

Ví dụ

Đầu vào 1:

4
2 6 3 11

Đầu ra 1:

1

Đầu vào 2:

3
4 9 15

Đầu ra 2:

4

Giải thích: Ở test đầu tiên, Per sẽ kết nối lá ~1~ và ~2~ với nhau và ăn ~0~ cái kẹo, kết nối lá ~2~ và ~3~ và ăn ~0~ cái kẹo, kết nối lá ~1~ và ~4~ và ăn ~1~ cái kẹo. Cả ~4~ lá đã được kết nối. Tổng số kẹo ăn là ~1~ — đây là đáp án tối thiểu.

Giới hạn

Trong tất cả các test: ~1 \le n \le 10^5~, ~1 \le p_i \le 10^7~.