國防部的軍事武器承包商剛完成一種新式飛彈防禦系統的測試工作,該系統稱為 CATCHER,可以攔截朝我方發射過來的飛彈,該系統非常強大,有極佳的機動性及自我防禦能力,但它有一個缺點:雖然它能攔截的飛彈高度沒有上限,但是能攔截的飛彈高度只能比上一次攔截的高度更低或相等,它沒有足夠的動力攔截更高的飛彈。
承包商所做的電腦模擬測試相當簡單,僅僅只做高度測試,也就是每隔一段時間就會有一顆欲攔截的飛彈,並顯示該飛彈可以被攔截到的高度,所有飛彈都是循序的。
測試報告中只會循序顯示所模擬的飛彈高度,及所有這些飛彈中可以被 CATCHER 攔截到的總數。
現在國防部需要驗證承包商所做的測試報告的正確性,你必須幫忙寫一個程式循序讀入多組飛彈高度,並計算 CATCHER 系統最多可攔截的飛彈總數,請注意到 CATCHER 系統本身的限制,當他選擇攔截某一顆飛彈之後,再也不能攔截更高的飛彈了。
Input
輸入包含多組測試資料,每組資料會有多非負整數,其值介於 0 ~ 32767 之間,用來表示飛彈的高度,測試資料的最後以 -1 表示該組資料結束,並非表示飛彈的高度。如果該組測試資料的第一個數值為 -1,表示測試資料結束。
Output
請輸出每組測試資料的編號 (Test #1
、Test #2
、…),及在該組資料下 CATCHER 系統所能攔截到的最大飛彈總數,輸出的格式如下所示。並請注意每組輸出資料之間請以空行隔開。
注意:每組測試資料的飛彈總數並沒有限制,所以一個效率不佳的演算法可能無法在時限內完成問題。
Sample Input
389
207
155
300
299
170
158
65
-1
23
34
21
-1
-1
Sample Output
Test #1:
maximum possible interceptions: 6
Test #2:
maximum possible interceptions: 2