C - AtCoder Riko 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

以下のようなことが起こりうる正整数 L をすべて求めてください。

AtCoder 社は棒状のスナック菓子「AtCoderりこ」を発売しました。 カップの中に長さ L の AtCoderりこが何本か入っています。 高橋君がこのカップをシェイクしたところ、それぞれの AtCoderりこは以下のいずれかの状態になりました。

  • 長さが L である 1 本の AtCoderりことしてそのまま残った。
  • 長さの和が L であるような 2 本の AtCoderりこに分かれた。ただし、各 AtCoderりこの長さは正整数である。
カップをシェイクした後、カップの中には N 本の AtCoderりこが入っており、i 本目の AtCoderりこの長さは A_i でした。

ただし、このようなことが起こりうる正整数 L が少なくとも 1 つ存在するような入力が与えられます。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 条件を満たすような L が少なくとも 1 つ存在する
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N  
A_1 A_2 \ldots A_N

出力

条件を満たすような L を、空白区切りで昇順に 1 行で出力せよ。

入力例 1

4
10 5 5 10

出力例 1

10 15

最初、カップには長さ 10 の AtCoderりこが 3 本入っていて、そのうち 1 本が 長さ 5 の 2 本の AtCoderりこに分かれると、条件を満たします。
最初、カップには長さ 15 の AtCoderりこが 2 本入っていて、それぞれの AtCoderりこが長さ 5,10 の 2 本の AtCoderりこに分かれると、条件を満たします。
これ以外の L では条件を満たしません。

入力例 2

3
4 4 4

出力例 2

4

入力例 3

6
10 187 344 100 434 257

出力例 3

444

Score : 350 points

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find all positive integers L for which the following can occur:

AtCoder Inc. has released a stick-shaped snack called "AtCoderiko." A cup contains one or more AtCoderikos, each of length L. When Takahashi shook the cup, each AtCoderiko ended up in one of the following states:

  • It remained as one AtCoderiko of length L.
  • It broke into two AtCoderikos whose lengths sum to L. Here, the length of each AtCoderiko is a positive integer.
After shaking the cup, there were N AtCoderikos in the cup, and the length of the i-th AtCoderiko was A_i.

The given input guarantees that there exists at least one positive integer L for which this can occur.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9
  • There exists at least one L satisfying the condition.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N  
A_1 A_2 \ldots A_N

Output

Output all values of L satisfying the condition in ascending order, separated by spaces, in one line.

Sample Input 1

4
10 5 5 10

Sample Output 1

10 15

If the cup initially contained three AtCoderikos of length 10, and one of them broke into two AtCoderikos of length 5, the condition is satisfied.
If the cup initially contained two AtCoderikos of length 15, and each of them broke into two AtCoderikos of lengths 5 and 10, the condition is satisfied.
No other values of L satisfy the condition.

Sample Input 2

3
4 4 4

Sample Output 2

4

Sample Input 3

6
10 187 344 100 434 257

Sample Output 3

444