TopCoder

User's AC Ratio

82.5% (47/57)

Submission's AC Ratio

30.3% (66/218)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 65536 65536
1 500 65536 65536
2 500 65536 65536
3 500 65536 65536
4 500 65536 65536
5 500 65536 65536
6 500 65536 65536
7 500 65536 65536
8 500 65536 65536
9 500 65536 65536