Bobo 在 ICPCCamp 学会了解决最长上升子序列问题后得到了一个长度为 $n$ 的数列 $p_1, p_2, \dots, p_n$.

Bobo 想用 $1, 2, \dots, n$ 来替换其中值为 $0$ 的元素，使得 $p_1, p_2, \dots, p_n$ 互不相同（即 $p_1, p_2, \dots, p_n$ 是 $\{1, 2, \dots, n\}$ 的排列）。

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

输入

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

每组数据的第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$).

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq n$).

保证 $p_1, p_2, \dots, p_n$ 中非 $0$ 的元素互不相同。

输出

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

样例输入

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

样例输出

4
9
1