TopCoder

C0DET1GER
OTZ

User's AC Ratio

95.2% (40/42)

Submission's AC Ratio

38.3% (49/128)

Tags

Description

初華在小祥生日時送給小祥一個生日禮物。

小祥打開來發現裡面是一個長度為 n 的非負整數陣列 a,小祥想要用陣列 a 生成出另外一個陣列 b

一開始 b 是一個空陣列,並且 1n 都未標記。每次操作小祥會選一個未標記的整數 i1in),並且維護一個初始值為 0 的整數 s,小祥會把所有在 1n 中為 i 的倍數且未被標記的整數 j 做標記,並且把 s 加上 aj,等到這次操作的標記都做完後,小祥會把 s 加進陣列 b 的後面。小祥會一直做操作直到 1n 都被標記了。

舉例來說,n=5,a=[3,7,6,5,2],假設小祥第一次操作選的 i=2,那 2,4 會被做上標記,並且 s=a2+a4=12,小祥會把 12 加進陣列 b 後面;第二次操作選的 i=55 會被做上標記,並且 s=a5=22 會被加進 b 後面;第三次操作選的 i=1,在 1 的倍數中未標記的數字有 1,31,3 會被做上標記且 s=a1+a3=99 會被加進 b 後面。因為 15 都被標記了,所以小祥會停止操作,並且得到一個長度為 3 的陣列 bb=[12,2,9]

小祥很好奇她能生成出最大字典序的陣列 b 是什麼,請你幫幫她!

Input Format

第一行有一個正整數 n
第二行有 n 個非負整數 a1an

對於所有測試資料:

  • 1n105
  • 0ai1041in

Output Format

第一行輸出 k 代表最大字典序陣列 b 的長度。
第二行輸出 k 個整數 b1bk

Sample Input 1

1
8

Sample Output 1

1
8

Sample Input 2

2
0 114

Sample Output 2

2
114 0

Sample Input 3

3
9999 0 1

Sample Output 3

1
10000

Hints

有兩個陣列 ABA 的字典序大於 B 代表:B 的長度小於 ABA 的前綴,或是存在一個位置 i1imin(|A|,|B|)),使得 Aj=Bj1j<i),且 Ai > Bi

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0, 3~6 ai>01in 18
3 7~9 ai=01in 18
4 0~1, 10~14 恰好有一個 i1in),使得 ai>0 27
5 0~24 無其他限制 37

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 4 5
1 1000 65536 65536 1 4 5
2 1000 65536 65536 1 5
3 1000 65536 65536 2 5
4 1000 65536 65536 2 5
5 1000 65536 65536 2 5
6 1000 65536 65536 2 5
7 1000 65536 65536 3 5
8 1000 65536 65536 3 5
9 1000 65536 65536 3 5
10 1000 65536 65536 4 5
11 1000 65536 65536 4 5
12 1000 65536 65536 4 5
13 1000 65536 65536 4 5
14 1000 65536 65536 4 5
15 1000 65536 65536 5
16 1000 65536 65536 5
17 1000 65536 65536 5
18 1000 65536 65536 5
19 1000 65536 65536 5
20 1000 65536 65536 5
21 1000 65536 65536 5
22 1000 65536 65536 5
23 1000 65536 65536 5
24 1000 65536 65536 5