A15490 | Valid Bitonic Permutations

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

An array of $n \ge 3$ elements is bitonic if its elements are first increasing till an index $k$ , $2 \le k \le n-1$ , and then decreasing till the end. For example, $[2,5,8,6,1]$ is a bitonic array with $k=3$ , but $[2,5,8,1,6]$ is not a bitonic array (elements first increase till $k=3$ , then decrease, and then increase again).

A bitonic permutation is a permutation in which the elements follow the above-mentioned bitonic property. For example, $[2,3,5,4,1]$ is a bitonic permutation, but $[2,3,5,1,4]$ is not a bitonic permutation (since it is not a bitonic array) and $[2,3,4,4,1]$ is also not a bitonic permutation (since it is not a permutation).

Sample Test Case Description

For $n=3$ , possible permutations are $[1,2,3]$ , $[1,3,2]$ , $[2,1,3]$ , $[2,3,1]$ , $[3,1,2]$ , and $[3,2,1]$ . Among the given permutations, the bitonic permutations are $[1,3,2]$ and $[2,3,1]$ .

In the first test case, the expected permutation must be of the form $[2,?,3]$ , which does not satisfy either of the two bitonic permutations with $n=3$ , therefore the answer is 0.

In the second test case, the expected permutation must be of the form $[?,3,2]$ , which only satisfies the bitonic permutation $[1,3,2]$ , therefore, the answer is 1.