Description

最长上升子序列的问题想必大家是耳熟能详的。
现在给出一个序列，其中的\(0\)可以被替换为任何数，不同的0可以被替换为不同的数，请最大化最长（严格）上升子序列的长度。

Format

Input

每个测试点包含不超过\(10\)组输入数据，请处理至文件结束。
每组数据第一行一个整数\(n(1<=n<=10^5)\)。
接下来一行\(n\)个非负整数，第\(i\)个整数\(a_i(0<=a_i<=10^9)\)表示序列的第\(i\)个元素。

Output

依照输入顺序，对于每组数据输出一行一个整数表示对应的结果。

Sample 1

Input

7
2 0 2 1 2 0 5
6
1 2 3 3 0 0

Output

5
5

Limitation

1s, 1GB for each test case.

Source

Vijos Original