問題文

長さがNNの数列AAが与えられます.この数列に対して,以下の操作を可能な限り繰り返すと,最後は数列の要素数が11になります.その数を出力してください.

操作

  1. 数列AAの中から,xyx \leq y を満たす任意の22つの数xxyyを取り出す.
  2. x=yx = y ならば,xxのみを数列AAに戻し,yyは削除する.
  3. x<yx \lt y ならば,xxyxy-x を数列AAに戻す.

(最後に残る数は一意に定まることが証明できます.)

制約

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

入力

NN
A1ANA_1 \dots A_N

出力

数列AAに対して,操作を可能な限り繰り返した後最後に残る数を出力.

サンプル

入力例1
5
126 282 96 132 72
出力例1
6

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

  1. 最初,数列AA[126,282,96,132,72][126, 282, 96, 132, 72] です.
  2. 126126282282 を取り出して 282126=156282-126=156 を行い,数列AA[126,156,96,132,72][126, 156, 96, 132, 72] にします.
  3. 126126156156 を取り出して 156126=30156-126=30 を行い,数列AA[126,30,96,132,72][126, 30, 96, 132, 72] にします.
  4. 126126132132 を取り出して 132126=6132-126=6 を行い,数列AA[126,30,96,6,72][126, 30, 96, 6, 72] にします.
  5. 9696126126 を取り出して 12696=30126-96=30 を行い,数列AA[30,30,96,6,72][30, 30, 96, 6, 72] にします.
  6. 72729696 を取り出して 9672=2496-72=24 を行い,数列AA[30,30,24,6,72][30, 30, 24, 6, 72] にします.
  7. 30307272 を取り出して 7230=4272-30=42 を行い,数列AA[30,30,24,6,42][30, 30, 24, 6, 42] にします.
  8. 30304242 を取り出して 4230=1242-30=12 を行い,数列AA[30,30,24,6,12][30, 30, 24, 6, 12] にします.
  9. 30303030 を取り出して片方を削除し,数列AA[30,24,6,12][30, 24, 6, 12] にします.
  10. 24243030 を取り出して 3024=630-24=6 を行い,数列AA[6,24,6,12][6, 24, 6, 12] にします.
  11. 12122424 を取り出して 2412=1224-12=12 を行い,数列AA[6,12,6,12][6, 12, 6, 12] にします.
  12. 12121212 を取り出して片方を削除し,数列AA[6,12,6][6, 12, 6] にします.
  13. 661212 を取り出して 126=612-6=6 を行い,数列AA[6,6,6][6, 6, 6] にします.
  14. 6666 を取り出して片方を削除し,数列AA[6,6][6, 6] にします.
  15. 6666 を取り出して片方を削除し,数列AA[6][6] にします.

最後に残る数は 66 です.

提出


Go (1.21)