题目描述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\leq n\leq 10^{5})\).

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

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

输出格式Output

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

样例Sample

出题Author

ftiasch

来源Source