大雄某日不小心用複製鏡複製了 n 個胖虎出來,這些胖虎在複製鏡效果結束之前只好先住在大雄家。
胖虎們都很喜歡唱歌,也都不喜歡聽到別的胖虎唱歌。
大雄與哆拉A夢當然也想遠離噪音,無論是大聲還是小聲。(因為實在太難聽)
因為大雄家很小, 在同一樓裡如果有胖虎唱歌都會聽到。
所以他們都不能盡興地唱歌,而他們不爽就會打大雄。
為了解救大雄,哆啦A夢拿出了樓層生產機器,但每個胖虎的聲音都很大,可能穿透樓層之間的牆壁。
問至少需要有幾樓才能使胖虎們都可無限歡唱,且大雄與哆拉A夢也不用忍受那恐怖的歌聲?
註: 樓層只能增加在任兩個樓層之間。所以大雄必住在頂樓,哆拉A夢必住在底樓。
有多筆測資,對於每筆測資,
第一行有一個數 n (1 <= n <= 100000),下一行有 n 個數(0 < ai < n)表示每個胖虎的音量。
聲音從胖虎所在層向上下發出,每穿透一層牆壁音量便會降低1。
音量為1即代表無法穿越牆壁。
若n = 0 時代表輸入結束。
對於每組輸入,輸出大雄家所需的最小樓層數。
※0.5 sec per testdata
原TIOJ1030 / KSHSVC 97,98 TOI初選練習(07/02/01 prob 1)
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 |