TopCoder

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

62.5% (5/8)

Tags

Description

有很多人相信,一個考試的成績分布應該要呈現常態分布,這個考試才是一個好的考試。正式地說,一場考試的成績分布是一個函數 ff(x)= 在這場考試中得分恰為 x 的人數,如果 f(x)「看起來很像常態分布」,那麼我們就說這是一場好的考試。至於什麼是「看起來像常態分布」,就是一個值得探討的問題了。

李教授開設的課程剛考完期末考,每個人的分數都是一個 0N 之間的整數,分數為 i 的人有 ai 個。李教授發現,其實眾人在乎的「看起來像常態分布」,真正的意思是分數對人數的長條圖呈現「中間高兩邊低」的樣貌,也就是存在唯一一個最高的長條,這個長條既不是最左邊的也不是最右邊的,並且其他長條的高度往最高長條的兩邊嚴格遞減,這樣一來眾人就會覺得成績分布看起來像常態分布。注意高度為 0 的長條也算是一個長條。

由於分數種類數多達 N+1 種,直接畫成每種分數一個長條的話,會有太多個長條,也不太好閱讀,因此李教授決定把切出一些分數區間,再為每一個分數區間畫一個長條,高度就是分數落在這個區間裡的人數。正式的說,李教授想把 0N 的整數分成若干個區間,假設他想要分成 K 個區間,第 i 個區間的第一個數是 pi,那麼第一個分數區間的範圍是 [p1,p21]、第二個是 [p2,p31]、第三個是 [p3,p41]、……、最後一個是 [pK,N](注意到 p1 總是為 0),他繪製的長條圖中會有 K 個長條,由左至右的第 i 個長條對應到第 i 個分數區間,分數在該區間裡的學生人數就是這個長條的高度。由於長條數量太少會很奇怪,所以必須要滿足 K3

李教授發現,使用不同切分數區間的方法時,畫出來的長條圖居然會截然不同!舉例來說,假設 N=15,下圖是直接畫出每一種分數對應到的人數的長條圖:

即便它長得一點也不像常態分布,只要適當的切割分數區間,就可以得到像這樣的長條圖:

這張圖中的分數區間數量是 5,5 個分數區間的左界分別是 0,3,6,9,14,長條下方寫出了每個區間的範圍(包含邊界)。這張長條圖是一張符合「看起來像常態分布」要求的長條圖。

請幫李教授決定好怎麼切分數區間,使得畫出來的長條圖看起來像常態分布。

Input Format

第一行包含一個整數 N,代表這個考試的最高分是 N。注意最低分是 0,因此實際上有 N+1 種分數。

第二行包含 N+1 個整數 a0,a1,,aN,代表獲得的分數為 i 的學生有 ai 人。

  • 2N105
  • 0ai109

Output Format

如果無論如何都無法畫出看起來像常態分布的長條圖,輸出 1

否則,輸出兩行:

  • 第一行包含一個整數 K,代表有幾個分數區間。
  • 第二行包含 K 個整數 p1,p2,,pK,意義如題目所述。

你輸出的答案必須滿足以下條件:

  • K3
  • 0=p1<p2<<pKN
  • 對於 1iK,令 pK+1=N+1hi=j=pipi+11aj,也就是分數在第 i 個分數區間中的學生人數,必須滿足存在 1<m<K,使得 h1<h2<<hm1<hm>hm+1>>hK

Sample Input 1

15
3 2 3 6 5 5 3 6 10 1 3 1 0 5 1 6

Sample Output 1

5
0 3 6 9 14

Sample Input 2

4
0 0 1 1 1

Sample Output 2

3
0 2 4

Sample Input 3

2
1 1 1

Sample Output 3

-1

Sample Input 4

4
0 0 0 0 0

Sample Output 4

-1

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~25 無額外限制 100

Testdata and Limits

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