CSG-CPC
Online Judge

1138 : 最长上升子序列

         Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 6     Solved: 1    

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 ≤ 105).

第二行包含 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

Author

ftiasch