How many ways are there to list the numbers 1 to 10 in some order such that every number is either greater or smaller than all the numbers before it?
(Problem source: Aops) The number of lists is $2^{9}=512$. Imagine building a list from the end. First, note that the last number must be 1 or 9 , since otherwise it would be less than some numbers before it and greater than others. Thus, there are two choices for the last number.

Similarly, after choosing the last number, the second to last number must be either the biggest number remaining or the smallest number remaining, since otherwise it would be less than some numbers before it and greater than some other numbers before it. Thus, we have two choices for the second to last number. similarly, there
are two choices for the 3rd number from the end once the last two are chosen, and so on until we reach the second number in the list. For the first number in the list, there is only one choice since there is only one number remaining. Putting this together, we've had 2 choices for each of the last 9 spots and 1 choice for the first, giving $2^{9}=512$ possible lists.