After learning how to solve the Longest Increasing Subsequence problem at ICPCCamp, Bobo obtained a sequence $p_1, p_2, \dots, p_n$ of length $n$.

Bobo wants to replace the elements with value $0$ using the numbers $1, 2, \dots, n$ such that $p_1, p_2, \dots, p_n$ are all distinct (i.e., $p_1, p_2, \dots, p_n$ becomes a permutation of $\{1, 2, \dots, n\}$).

Now, Bobo wants to know the number of such sequences where the length of the longest increasing subsequence is exactly $(n - 1)$ after the replacement.

Input

The input contains no more than $300$ test cases, with at most $20$ cases where $n > 100$.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$).

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \leq p_i \leq n$).

It is guaranteed that the non-zero elements in $p_1, p_2, \dots, p_n$ are distinct.

Output

For each test case, output a single integer representing the required value.

Examples

Input 1

3
0 0 0

Output 1

4

Input 2

4
0 0 0 0

Output 2

9

Input 3

5
1 0 0 4 5

Output 3

1