#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
DSU(int n) {
p.resize(n);
sz.resize(n, 1);
for(int i = 0; i < n; i++){
p[i] = i;
}
}
int find(int x) {
return (p[x] == x ? x : p[x] = find(p[x]));
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a,b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> arr(N);
long long maxVal = 0;
for(int i = 0; i < N; i++){
cin >> arr[i];
if(arr[i] > maxVal) maxVal = arr[i];
}
// DSU for connecting the N cards themselves
DSU dsu(N);
// pos[v] = indices of all cards whose value is v
static vector<int> pos[100001]; // since Pi <= 1e5
for(int v = 0; v <= 100000; v++){
pos[v].clear();
}
for(int i = 0; i < N; i++){
pos[arr[i]].push_back(i);
}
// First, unite all duplicate cards of the same value at cost 0
for(int v = 1; v <= 100000; v++){
if(pos[v].size() > 1){
for(size_t i = 1; i < pos[v].size(); i++){
dsu.unite(pos[v][0], pos[v][i]);
}
}
}
// rep[v] = an index (a “representative card”) that has value v,
// or -1 if v does not appear
vector<int> rep(100001, -1);
for(int v = 1; v <= 100000; v++){
if(!pos[v].empty()){
rep[v] = pos[v][0];
}
}
// Now, add zero‐cost edges where one value divides another.
// For each v, if it appears, unite it with all multiples of v.
// That gives cost = min(v mod m, m mod v) = 0 if v|m.
for(int v = 1; v <= maxVal; v++){
if(rep[v] == -1) continue; // value v not in array
// We only sieve up to maxVal
for(long long mult = 2LL*v; mult <= maxVal; mult += v){
if(mult <= 100000 && rep[mult] != -1){
dsu.unite(rep[v], rep[mult]);
}
}
}
// Next, gather all *distinct* values that actually appear
// (in ascending order) so we can link “neighboring” values.
vector<long long> distinct;
distinct.reserve(N);
for(int v = 1; v <= maxVal; v++){
if(rep[v] != -1){
distinct.push_back(v);
}
}
// Build candidate edges between consecutive distinct values.
// cost = min(x % y, y % x). If x < y then cost = y % x.
// We'll just do y % x for consecutive ascending x < y.
vector<array<long long,3>> edges; // {cost, rep_of_x, rep_of_y}
for(int i = 0; i + 1 < (int)distinct.size(); i++){
long long x = distinct[i];
long long y = distinct[i+1];
// since x < y, cost = y mod x
long long c = y % x;
edges.push_back({c, rep[x], rep[y]});
}
// Sort these edges by cost ascending
sort(edges.begin(), edges.end(),
[](auto &a, auto &b){return a[0] < b[0];});
// Finally, Kruskal over those edges to connect any remaining
// components. We track how many DSU components remain in the
// full set of N cards.
// (In principle we could track it just among the distinct reps,
// but it’s simpler to count the DSU parents of all N.)
long long ans = 0;
// Count how many DSU "leaders" are in the entire array
int compCount = 0;
for(int i = 0; i < N; i++){
if(dsu.find(i) == i) compCount++;
}
// Kruskal: smallest edges first
for(auto &e : edges){
long long c = e[0];
int a = e[1], b = e[2];
if(dsu.unite(a,b)){
ans += c;
compCount--;
if(compCount == 1) break; // all cards connected
}
}
cout << ans << "\n";
return 0;
}
