Given a permutation, we can define its high-water marks as the indices in which its cumulative maximum increases, or, equivalently, indices with values bigger than all previous values.
For example, the permutation \$ 4, 2, 3, 7, 8, 5, 6, 1 \$, with a cumulative maximum of \$ 4, 4, 4, 7, 8, 8, 8, 8 \$ has \$1, 4, 5\$ as (1-indexed) high-water marks, corresponding to the values \$4, 7, 8\$.
Given a list of indices and a number \$n\$, generate some permutation of size \$n\$ with the list as its high-water marks in time polynomial in \$n\$.
This is code golf, so the shortest solution in each language wins.
In all of those except the first, more than one valid permutation exist, and you may output any one of them.
1-based high-water mark indices, n -> a valid permutation [1, 2, 3], 3 -> [1, 2, 3] [1, 2, 3], 5 -> [2, 3, 5, 4, 1] [1, 4, 5], 8 -> [4, 2, 3, 7, 8, 5, 6, 1] , 5 -> [5, 4, 3, 2, 1] [1, 5], 6 -> [4, 1, 3, 2, 6, 5]
- You can use any reasonable I/O format. In particular, you can choose:
- To take the input list as a bitmask of size \$n\$, and if you do that whether to take the size at all.
- Whether the input is 0-indexed or 1-indexed.
- Whether to have the first index (which is always a high-water mark) in the input. When taking a bitmask, you may take a bitmask of size \$n-1\$ without the first value. When taking a list of indices, you can have it indexed ignoring the first value.
- Whether the output is a permutation of the values \$0,1,...,n-1\$ or \$1,2,...,n\$.
- To output any non-empty set of the permutations, as long as the first permutation is outputted in polynomial time.
- To have the cumulative minimum decrease in the given points instead.
- To have the cumulative operation work right-to-left, instead of left-to-right.
- It is allowed for your algorithm to be non-deterministic, as long as it outputs a valid permutation with probability 1 and there's a polynomial \$p(n)\$ such that the probability it takes more than \$p(n)\$ time to run is negligible. The particular distribution doesn't matter.
- Standard loopholes are disallowed.