cf228 div2 A. Fox and Number Game (模拟）

题意大致就是在给出的数列中不断取出 i，j 两个数，ai>aj , 然后把 ai-aj重新放入，直到不能做为止

我用了个优先队列模拟。因为可能同时有几个最大值。。所以不能单纯的比较最大值和后面一个最大值相等就停止

题目：

Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x₁, x₂, ..., x_n. She can do the following operation as many times as needed: select two different indexes i and j such that x_i > x_j hold, and then apply assignment x_i = x_i - x_j. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input

The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x₁, x₂, ..., x_n (1 ≤ x_i ≤ 100).

Output

Output a single integer — the required minimal sum.

Sample test(s)

Input

2
1 2

Output

Input

3
2 4 6

Output

Input

2
12 18

Output

Input

5
45 12 27 30 18

Output

Note

In the first example the optimal way is to do the assignment: x₂ = x₂ - x₁.

In the second example the optimal sequence of operations is: x₃ = x₃ - x₂, x₂ = x₂ - x₁.

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <vector>
 5 #include <queue>
 6 #include <stack>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <string>
10 #include <cstdlib>
11 using namespace std;
12 #define LL lolng long
13 const double pi = acos(0.) * 2;
14 priority_queue<int >q;
15 vector<int> ans;
16 int n;
17 int num[200];
18 int main()
19 {
20     scanf("%d", &n);
21     for(int i=0;i<n;i++)
22     {
23         int d;
24         scanf("%d",&d);
25         q.push(d);
26     }
27     long long ret =0;
28     while(1)
29     {
30         int f,s;
31         f = q.top();q.pop();
32         if( f==q.top())
33         {
34             ans.push_back(f);
35             while(!q.empty()&&f == q.top())
36             {
37                 f= q.top();
38                 ans.push_back(q.top());q.pop();
39             }
40             if(!q.empty())
41             {
42                 int p = ans.front();
43                 ans.pop_back();
44                 q.push( p-q.top());
45                 for(int i=0;i<ans.size();i++)
46                     q.push(p);
47                 ans.clear();
48             }
49             else
50                 break;
51         }
52         else
53             q.push(f-q.top());
54     }
55 
56     while(!ans.empty())
57     {
58         ret+= ans.back();
59         ans.pop_back();
60     }
61     printf("%d
",ret);
62     return 0;
63 }