Valley Permutations of Given Length

Given a non-negative integer n return the number of valley permutations of length n

A valley permutation is defined as a permutation that is a concatenation of two parts: a monotonically decreasing sequence and then a monotonically increasing sequence

Example:

Input: n = 4
Output: 8
Explanation: [
    [1, 2, 3, 4],
    [2, 1, 3, 4],
    [3, 1, 2, 4],
    [3, 2, 1, 4],
    [4, 1, 2, 3],
    [4, 2, 1, 3],
    [4, 3, 1, 2],
    [4, 3, 2, 1]
]