Sir Alex is coaching a soccer team of $n$ players of distinct heights. He wants to line them up so that for each player $P$, the total number of players that are either to the left of $P$ and taller than $P$ or to the right of $P$ and shorter than $P$ is even. In terms of $n$, how many possible orders are there?

[i]Michael Ren[/i]
1. **Define the problem and notation:**
   - We have \( n \) players with distinct heights.
   - We need to line them up such that for each player \( P \), the total number of players either to the left of \( P \) and taller than \( P \) or to the right of \( P \) and shorter than \( P \) is even.
   - Let the heights be ordered as \( 1, 2, 3, \ldots, n \).
   - Let \( a_k \) be the height of the player in position \( k \).

2. **Analyze the condition:**
   - For each player \( k \), let \( p \) be the number of players to the left of \( k \) who are shorter than \( k \).
   - Then, \( k - p - 1 \) players are to the left of \( k \) and taller than \( k \).
   - The number of players to the right of \( k \) who are shorter than \( k \) is \( a_k - p - 1 \).
   - The total number of players either to the left of \( k \) and taller than \( k \) or to the right of \( k \) and shorter than \( k \) is:
     \[
     (k - p - 1) + (a_k - p - 1) = a_k + k - 2p - 2
     \]

3. **Condition for evenness:**
   - The expression \( a_k + k - 2p - 2 \) must be even.
   - Since \( 2p \) is always even, \( a_k + k - 2 \) must be even.
   - Therefore, \( a_k + k \) must be even.

4. **Parity condition:**
   - For \( a_k + k \) to be even, \( a_k \) and \( k \) must have the same parity (both even or both odd).
   - This means that \( a_k \equiv k \pmod{2} \).

5. **Counting valid permutations:**
   - We need to assign even positions to even heights and odd positions to odd heights.
   - There are \( \lfloor \frac{n}{2} \rfloor \) even numbers and \( \lceil \frac{n}{2} \rceil \) odd numbers.
   - The number of ways to permute the even numbers among the even positions is \( \lfloor \frac{n}{2} \rfloor! \).
   - The number of ways to permute the odd numbers among the odd positions is \( \lceil \frac{n}{2} \rceil! \).

6. **Final calculation:**
   - The total number of valid orders is:
     \[
     \lfloor \frac{n}{2} \rfloor! \cdot \lceil \frac{n}{2} \rceil!
     \]

Conclusion:
\[
\boxed{\lfloor \frac{n}{2} \rfloor! \cdot \lceil \frac{n}{2} \rceil!}
\]