#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using VVI = vector>; using VVL = vector>; using VI = vector; using VL = vector; using VS = vector; using VC = vector; using VP = vector>; using Graph0 = vector>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--) #define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++) #define lrep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--) #define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++) #define arep(i, v) for (auto i : v) #define all(a) (a).begin(), (a).end() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define eyes cout << "Yes" << endl;exit(0); #define eno cout << "No" << endl;exit(0); template bool chmax(T &a, const T& b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T& b) { if (a > b) { a = b; return true; } return false; } template void excout(T A) { cout << A << endl; exit(0); } constexpr long long INF = (1LL << 60); // INFにちゅういい! // 辺の情報 struct Edge { // 行先 int to; // コスト int cost; }; using Graph = std::vector>; // { distance, from } using Pair = std::pair; // ダイクストラ法 (1.1 基本実装) // distances は頂点数と同じサイズ, 全要素 INF で初期化しておく void Dijkstra(const Graph& graph, std::vector& distances, int startIndex) { // 「現時点での最短距離, 頂点」の順に取り出す priority_queue // デフォルトの priority_queue は降順に取り出すため std::greater を使う std::priority_queue, std::greater> q; q.emplace((distances[startIndex] = 0), startIndex); while (!q.empty()) { const long long distance = q.top().first; const int from = q.top().second; q.pop(); // 最短距離でなければ処理しない if (distances[from] < distance) { continue; } // 現在の頂点からの各辺について for (const auto& edge : graph[from]) { // to までの新しい距離 const long long d = (distances[from] + edge.cost); // d が現在の記録より小さければ更新 if (d < distances[edge.to]) { q.emplace((distances[edge.to] = d), edge.to); } } } } template T MODS(T a, T mods) { return ((((((a + mods) % mods) + mods) % mods))); } //combination 列挙用 --int ver VVI comb(int n, int r) { VVI v(n + 1, VI (n + 1, 0)); for (int i = 0; i < v.size(); i++) { v[i][0] = 1; v[i][i] = 1; } for (int j = 1; j < v.size(); j++) { for (int k = 1; k < j; k++) { v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]); } } return v; } vector > prime_factorize(long long N) { // 答えを表す可変長配列 vector > res; // √N まで試し割っていく for (long long p = 2; p * p <= N; ++p) { // N が p で割り切れないならばスキップ if (N % p != 0) { continue; } // N の素因数 p に対する指数を求める int e = 0; while (N % p == 0) { // 指数を 1 増やす ++e; // N を p で割る N /= p; } // 答えに追加 res.emplace_back(p, e); } // 素数が最後に残ることがありうる if (N != 1) { res.emplace_back(N, 1); } return res; } using UNION_TYPE = int; struct UnionFind { vector par, siz; UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {} UNION_TYPE root(UNION_TYPE x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } bool issame(UNION_TYPE x, UNION_TYPE y) { return root(x) == root(y); } bool unite(UNION_TYPE x, UNION_TYPE y) { x = root(x);y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } UNION_TYPE size(UNION_TYPE x) { return siz[root(x)]; } }; //mod func の型に注意!!! //Union Find はUNION_TYPE で型変可能! // VI topo_sort(Graph0& G) { int N = G.size(); VI IND(N, 0); rep(v, N) { arep(nv, G[v]) { IND[nv]++; } } queue que; rep(v, N) { if (IND[v] == 0) { que.push(v); } } VI ANS; while (!que.empty()) { int v = que.front(); ANS.push_back(v); que.pop(); arep(nv, G[v]) { IND[nv]--; if (IND[nv] == 0) { que.push(nv); } } } return ANS; } void ADD(int a, int b, Graph0& G) { G[a].push_back(b); G[b].push_back(a); } VP near(int i, int j, int H, int W) { VP ans; VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}}; arep(v, cand) { if (v.first < 0 or v.first >= H) continue; if (v.second < 0 or v.second >= W) continue; ans.push_back(v); } return ans; } int cast(int i, int j, int H, int W) { return ((W * i) + j); } ll pows(ll x, ll n, ll mod) { if (!n) return 1; x %= mod; ll r = pows(x, n / 2, mod); (r *= r) %= mod; if (n % 2) (r *=x) %= mod; return r; } struct COMB_MOD { ll mod; int MAX; VL fac, finv, inv; COMB_MOD(int max, ll m) { fac.assign(max, 0); finv.assign(max, 0); inv.assign(max, 0); mod = m; MAX = max; } void solve() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod%i] * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i] % mod; } } ll comb(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % mod) % mod; } }; struct LCA { vector> parent; // parent[k][u]:= u の 2^k 先の親 vector dist; // root からの距離 LCA(const Graph0 &G, int root = 0) { init(G, root); } // 初期化 void init(const Graph0 &G, int root = 0) { int V = G.size(); int K = 1; while ((1 << K) < V) K++; parent.assign(K, vector(V, -1)); dist.assign(V, -1); dfs(G, root, -1, 0); for (int k = 0; k + 1 < K; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } // 根からの距離と1つ先の頂点を求める void dfs(const Graph0 &G, int v, int p, int d) { parent[0][v] = p; dist[v] = d; for (auto e : G[v]) { if (e != p) dfs(G, e, v, d + 1); } } int query(int u, int v) { if (dist[u] < dist[v]) swap(u, v); // u の方が深いとする int K = parent.size(); // LCA までの距離を同じにする for (int k = 0; k < K; k++) { if ((dist[u] - dist[v]) >> k & 1) { u = parent[k][u]; } } // 二分探索で LCA を求める if (u == v) return u; for (int k = K - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; } }; int main(void) { int N;cin >> N; VL A(N + 1, 0); rep(i, N) cin >> A[i + 1]; sort(all(A)); VL S(N + 1, 0); urep(i, 1, N) S[i] = A[i] + S[i - 1]; ll ans = 0; urep(i, 1, N) { ll l = A[i]; ll r = 2 * A[i]; while (true) { // cout << A[i] << " " << l << " " << r << endl; auto itr = lower_bound(all(A), l); if (itr == A.end()) break; if (*itr >= r) { l += A[i]; r += A[i]; continue; } auto itr2 = lower_bound(all(A), r); itr2--; int x = itr - A.begin();int y = itr2 - A.begin(); //cout << "X" << x << " "<< y << endl; ll cnt = y - x + 1; ans += (S[y] - S[x - 1]) - (l * cnt); l += A[i];r += A[i]; } auto itr = lower_bound(all(A), A[i]); itr--; int ind = itr - A.begin(); ans += S[ind]; } cout << ans << endl; }