#include <bits/stdc++.h>
using namespace std;
// Typedefs and macros (as in your original code)
typedef long long ll;
typedef long double ld;
using str = string;
template <class T> using P = pair<T, T>;
using pi = P<int>;
using pl = P<ll>;
using pd = P<ld>;
using weg = pair<int, pi>; // weighted edge
#define mp make_pair
#define f first
#define s second
template <class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
using vd = V<ld>;
using vb = V<bool>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
using vvi = V<vi>;
using vweg = V<weg>;
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int ilb(V<T>& a, const T& b) {return int(lb(all(a), b) - (a).begin());}
template<class T> int iub(V<T>& a, const T& b) {return int(ub(all(a), b) - (a).begin());}
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (a); i >= (b); --i)
#define rep(a) FOR (_, 0, a)
#define each(a, x) for (auto& a: x)
#define trace(x) each(a, (x)) {cout << a << " ";}
#define tracel(x) each(a, (x)) {cout << a << "\n";}
// DSU variables and functions
vi parent;
vi size_ds;
int fs(int v) {
if (v == parent[v]) {
return v;
}
return parent[v] = fs(parent[v]);
}
void unite_sets(int u, int v) {
u = fs(u);
v = fs(v);
if (u != v) {
if (size_ds[u] < size_ds[v]) swap(u, v);
parent[v] = u;
size_ds[u] += size_ds[v];
}
}
void solve() {
int n;
cin >> n;
int largest = -1; // the largest value of a node
vi p(n);
FOR(i, 0, n) {
cin >> p[i];
largest = max(largest, p[i]);
}
// Step 1: remove duplicates and sort
set<int> ts(all(p));
p.assign(all(ts));
n = p.size();
srt(p);
// Step 2: clever pruning
vi next_largest_node(largest + 1, -1);
FOR(i, 0, n) {
next_largest_node[p[i]] = i;
}
ROF(i, largest - 1, 0) {
if (next_largest_node[i] == -1) {
next_largest_node[i] = next_largest_node[i + 1];
}
}
// Step 3: make edges
parent.resize(n);
size_ds.resize(n, 1);
iota(all(parent), 0);
vweg edges;
// Add edges between consecutive cards
FOR(i, 0, n - 1) {
edges.pb(mp(p[i + 1] % p[i], mp(i + 1, i)));
}
// Add edges based on multiples
FOR(i, 0, n) {
for (int curval = 2 * p[i]; curval <= largest; curval += p[i]) {
int next_node = next_largest_node[curval];
if (next_node != -1) { // Ensure valid index
edges.pb(mp(p[next_node] % p[i], mp(next_node, i)));
}
}
}
// Step 4: sort edges by cost
srt(edges);
// Step 5: Kruskal's algorithm to find MST
ll cost = 0;
for(auto &edge : edges) {
int ec = edge.f;
int u = edge.s.f;
int v = edge.s.s;
int set_u = fs(u);
int set_v = fs(v);
if (set_u != set_v) {
unite_sets(u, v);
cost += (ll) ec;
}
}
cout << cost << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
solve();
}
