TopCoder

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

60.0% (3/5)

Tags

Description

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

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

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

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

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

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

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

Input Format

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

第二行包含 $N+1$ 個整數 $a_0,a_1,\dots,a_N$,代表獲得的分數為 $i$ 的學生有 $a_i$ 人。

  • $2 \leq N \leq 10^ 5$
  • $0 \leq a_i \leq 10^ 9$

Output Format

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

否則,輸出兩行:

  • 第一行包含一個整數 $K$,代表有幾個分數區間。
  • 第二行包含 $K$ 個整數 $p_1,p_2,\dots,p_K$,意義如題目所述。

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

  • $K \geq 3$
  • $0=p_1 < p_2 < \dots < p_K \leq N$
  • 對於 $1 \leq i \leq K$,令 $p_{K + 1} = N + 1$ 且 $h_i=\sum_ {j=p_i}^ {p_{i+1}-1} a_j$,也就是分數在第 $i$ 個分數區間中的學生人數,必須滿足存在 $1 < m < K$,使得 $h_1 < h_2 < \dots < h_{m-1} < h_m > h_{m + 1} > \dots > h_K$

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