← 返回题目列表

AtCoder · arc105_b

B. 最大值-=最小值

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

Snuke 有 N 卡片编号 1 通过 N。 每张卡片上都写有一个整数;写在卡片上 i is a_i.

Snuke 执行了以下过程:

  1. 让 X 和 x 分别是 Snuke 卡上写的最大值和最小值。
  2. If X = x,终止程序。否则,更换每张卡 卡片上写有 X , 写入 X-x ,然后返回步骤 1。

在本问题的约束下,可以证明程序最终会终止。完成该程序后,找到所有 Snuke 卡上写的数字。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 \cdots a_N

输出

完成该程序后,打印写在所有 Snuke 卡上的数字。


示例输入 1

3
2 6 6

示例输出 1

2
  • 在程序开始时,Snuke 卡片上写的数字是 (2,6,6).
    • 自从 x=2 和 X=6,他替换每张牌 6 , 写入 4 。
  • 现在,Snuke 卡片上写的数字是 (2,4,4).
    • 自从 x=2 和 X=4,他替换每张牌 4 , 写入 2 。
  • 现在,Snuke 卡片上写的数字是 (2,2,2).
    • 自从 x=2 和 X=2,他终止程序。

示例输入 2

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

示例输出 2

42