1138 : 最长上升子序列

Description

Bobo 在 ICPCCamp 学会了解决最长上升子序列问题后得到了一个长度为 n 的数列 p1,p2,…,pn.

Bobo 想用 1,2,…,n 来替换其中值为 0 的元素，使得 p1,p2,…,pn 互不相同（即 p1,p2,…,pn 是 {1,2,…,n} 的排列）。

现在 Bobo 想知道，替换后最长上升子序列的长度恰好为 (n-1) 数列的数量。

Input

输入包含不超过 300 组数据，其中不超过 20 组的 n 超过 100.

每组数据的第一行包含一个整数 n(1 ≤ n ≤ 10⁵).

第二行包含 n 个整数p1,p2,…,pn (0 ≤ pi ≤ n).

保证p1,p2,…,pn中非 0 的元素互不相同。

Output

对于每组数据，输出一个整数表示要求的值。

Sample

3
0 0 0
4
0 0 0 0
5
1 0 0 4 5

4
9
1

Hint

Source

Author

ftiasch