Problem Statement

Six people, all of different heights, stand in a line (a left-to-right ordering; all six positions are filled). Number the people by height so that person 1 is the tallest and person 6 is the shortest, i.e. person k is the k -th tallest. An arrangement is called valid if, for every k with 1 <= k <= 6, the k -th tallest person stands immediately next to the (k+1) -th tallest person or immediately next to the (k-1) -th tallest person (or both). In particular, the tallest person must stand next to the second tallest person, and the shortest person must stand next to the second shortest person. How many valid arrangements of the six people are there?