TopCoder

User's AC Ratio

91.1% (92/101)

Submission's AC Ratio

37.2% (137/368)

Tags

Description

大雄某日不小心用複製鏡複製了 n 個胖虎出來,這些胖虎在複製鏡效果結束之前只好先住在大雄家。
胖虎們都很喜歡唱歌,也都不喜歡聽到別的胖虎唱歌。
大雄與哆拉A夢當然也想遠離噪音,無論是大聲還是小聲。(因為實在太難聽)
因為大雄家很小, 在同一樓裡如果有胖虎唱歌都會聽到。
所以他們都不能盡興地唱歌,而他們不爽就會打大雄。
為了解救大雄,哆啦A夢拿出了樓層生產機器,但每個胖虎的聲音都很大,可能穿透樓層之間的牆壁。
問至少需要有幾樓才能使胖虎們都可無限歡唱,且大雄與哆拉A夢也不用忍受那恐怖的歌聲?

註: 樓層只能增加在任兩個樓層之間。所以大雄必住在頂樓,哆拉A夢必住在底樓。

Input Format

有多筆測資,對於每筆測資,
第一行有一個數 n (1 <= n <= 100000),下一行有 n 個數(0 < ai < n)表示每個胖虎的音量。
聲音從胖虎所在層向上下發出,每穿透一層牆壁音量便會降低1。
音量為1即代表無法穿越牆壁。
若n = 0 時代表輸入結束。

Output Format

對於每組輸入,輸出大雄家所需的最小樓層數。

Sample Input

3
2 3 5
0

Sample Output

16

Hints

※0.5 sec per testdata

Problem Source

原TIOJ1030 / KSHSVC 97,98 TOI初選練習(07/02/01 prob 1)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 2
2 500 65536 262144 3
3 500 65536 262144 4
4 500 65536 262144 5
5 500 65536 262144 6
6 500 65536 262144 7
7 500 65536 262144 8
8 500 65536 262144 9
9 500 65536 262144 10