問題文

長さが$N$の数列$A$が与えられます．この数列に対して，以下の操作を可能な限り繰り返すと，最後は数列の要素数が$1$になります．その数を出力してください．

操作

1. 数列$A$の中から，$x \leq y$ を満たす任意の$2$つの数$x$，$y$を取り出す．
2. $x = y$ ならば，$x$のみを数列$A$に戻し，$y$は削除する．
3. $x \lt y$ ならば，$x$ と $y-x$ を数列$A$に戻す．

（最後に残る数は一意に定まることが証明できます．）

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{18} \quad (1 \leq i \leq N)$
• 入力はすべて整数

入力

出力

数列$A$に対して，操作を可能な限り繰り返した後最後に残る数を出力．

サンプル

5
126 282 96 132 72

6

例えば以下の順で操作します．

0. 最初，数列$A$は $[126, 282, 96, 132, 72]$ です．
1. $126$ と $282$ を取り出して $282-126=156$ を行い，数列$A$を $[126, 156, 96, 132, 72]$ にします．
2. $126$ と $156$ を取り出して $156-126=30$ を行い，数列$A$を $[126, 30, 96, 132, 72]$ にします．
3. $126$ と $132$ を取り出して $132-126=6$ を行い，数列$A$を $[126, 30, 96, 6, 72]$ にします．
4. $96$ と $126$ を取り出して $126-96=30$ を行い，数列$A$を $[30, 30, 96, 6, 72]$ にします．
5. $72$ と $96$ を取り出して $96-72=24$ を行い，数列$A$を $[30, 30, 24, 6, 72]$ にします．
6. $30$ と $72$ を取り出して $72-30=42$ を行い，数列$A$を $[30, 30, 24, 6, 42]$ にします．
7. $30$ と $42$ を取り出して $42-30=12$ を行い，数列$A$を $[30, 30, 24, 6, 12]$ にします．
8. $30$ と $30$ を取り出して片方を削除し，数列$A$を $[30, 24, 6, 12]$ にします．
9. $24$ と $30$ を取り出して $30-24=6$ を行い，数列$A$を $[6, 24, 6, 12]$ にします．
10. $12$ と $24$ を取り出して $24-12=12$ を行い，数列$A$を $[6, 12, 6, 12]$ にします．
11. $12$ と $12$ を取り出して片方を削除し，数列$A$を $[6, 12, 6]$ にします．
12. $6$ と $12$ を取り出して $12-6=6$ を行い，数列$A$を $[6, 6, 6]$ にします．
13. $6$ と $6$ を取り出して片方を削除し，数列$A$を $[6, 6]$ にします．
14. $6$ と $6$ を取り出して片方を削除し，数列$A$を $[6]$ にします．

最後に残る数は $6$ です．