It seems to me that the largest of the n numbers is necessarily the maximum. The other (n-1) are either on the left or the right of the maximum. Those on the left are in ascending order and those on the right are in descending order. For each of the other (n-1), the only question is whether it is on the left or the right. So there should be 2^(n-1) permutations that work.
First Thoughts (spoiler?)
