Generate Valley Permutations

Given a positive integer n, return all the 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.

E.g. valley permutations follow this format: [p[0] > p[1] > p[2] > ... > p[k] < p[k+1] < p[k+2] < ... < p[n-1]].

Example:

Input: n = 4

Output:[
    [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]
]

Explanation:
Permutations such as [1, 4, 2, 3] are not valleys because 1 < 4 > 2 < 3

Notes: n <= 10