12002 - Happy Birthday

當生日派對結束之後,大家拍拍屁股走人,留下壽星一個人整理客廰,他開始把客廳桌上的盤子拿到廚房清洗,他雖然很強壯可以一次拿得動所有盤子,但是卻害怕自已笨手笨腳打破盤子,所以希望所收捨的盤子可以穩穩地疊在一起,避免拿到廚房的途中摔破盤子而花上更多時間清理。讓盤子穩穩地疊在一起的方法是下層的盤子必須大於或等於上層盤子的大小。

一開始他兩手空空站在桌旁的一端,他沿著桌子走到另一端,沿途選擇一些盤子拿在手上,每當他發現一個盤子時,他可以:

  • 不理它。
  • 如果他手上沒有盤子,他可以拿起那個盤子。
  • 如果他手上有一疊盤子,他可以拿起桌上的盤子放到手上的那疊盤子上。
  • 如果他手上有一疊盤子,他可以把手上的盤子疊在桌上的盤子上,再把整盤拿在手上 (包含最下面的那個)。

他希望儘可能地拿最多盤子到廚房,請你幫他選擇取盤子的順序。

Input

輸入有多筆測試資料,每組資料兩列,第一列有一個整數 $N$ ($1\leq{N}\leq{500}$) 表示桌上盤子的總數,第二列有 $N$ 個整數 $k_1,k_2,\ldots{},k_n$ ($1\leq{k_i}\leq{1000}$) 依序表示他沿途發現的盤子大小。當 $N = 0$ 表測試資料結束。

Output

請每組測試資料輸出一趟最多可以收拾幾個盤子。

Sample Input

6
3 1 5 6 2 4
6
3 4 2 5 2 6
0

Sample Output

4
6