"指揮官!指揮官!趕快醒醒!"
"mmmm... 現在幾點了?"
"清晨4點零七分,我們剛收到國防部的緊急電報,請指揮官裁示。"
你不甘願的拿過電報,揉揉眼睛,看到上面寫著:
親愛的指揮官: 代誌大條了!昨天晚上俄羅斯瘋狂的Boris將軍伏特加喝多了,今天清晨時,原本要把鬧鐘按掉的,他...... 我直接說好了,現在正有好幾枚洲際飛彈朝你那邊飛去。更不幸的是,我們只知道飛彈的高度以及到達 的順序。趕快去處理吧!祝你好運! 國防部部長敬上 P.S. Hilly和Bill要我和你說嗨!
死啦!死啦!由於國防預算被刪減的緣故,你的愛國者反飛彈系統有嚴重的缺陷,發射的角度只能升不能降。也就是說,當你摧毀一枚來襲的飛彈之後,下一次你只能摧毀比上一枚飛得高的飛彈。例如:如果飛彈朝你飛來的高度分別是1,6,2,3,5(按照到達的順序),若你攔截了前2枚,那後面那3枚將無法再攔截。因為2,3,5都比6小。你的任務就是要攔截最多的飛彈數。
俄羅斯戰術非常奇怪,他們的將軍都是對數學準確非常執著的人。所以他們的飛彈總是以一種特別的順序來發射,使得上面所描述的問題只會有一組解答。
Input
輸入的第1列有一個整數N,代表以下有幾組測試資料。然後空一列。接下來的各列每列有一個整數,代表來襲飛彈的高度(按照飛彈到達的順序)。測試資料間空一列,請參考Sample Input。
Output
對每一組測試資料,請先輸出最多可以攔截幾枚飛彈。接下來的各列為所攔截到的飛彈的高度(按照他們到達的順序)。測試資料間空一列,請參考Sample Output。
Sample Input
2 1 6 2 3 5 3 7
Sample Output
Max hits: 4 1 2 3 5 Max hits: 2 3 7