Rephrase of scenario: each car overtakes a different number of cars and is overtaken by same number of cars. Let $ C_1, ... , C_n$ be the cars. Suppose $ C_i$ overtakes $ m_i$ cars and is overtaken by $ n_i$ cars. Since $ m_i \in \{0, \dots, n-1\}$, and all $ m_i$'s are distinct, each of $ 0, ... , n-1$ must occur exactly once. Thus the sum of $ m_i$'s is $ n(n-1)/2$. Since all the $ n_i$'s are equal, each $ n_i = (n-1)/2$. In summary $ n$ must be odd. Conversely, suppose $ n$ is odd. We show, by induction on $ n$, that the scenario is possible such that the first $ (n+1)/2$ cars remain in the first $ (n+1)/2$ positions - though possibly shuffled, or the first $ (n-1)/2$ cars remain in the first $ (n-1)/2$ positions. Write the cars in the order (left = back): \[ A, C_1, \dots, C_{(n-3)/2}, B, C_{(n-1)/2}, \dots, C_{n-2}.\] Then the following may happen: (i) $ B$ is overtaken by $ C_{(n-3)/2}, \dots, C_2, C_1$ so it comes between $ A$ and $ C_1$. \[ A, B, C_1, \dots, C_{(n-3)/2}, C_{(n-1)/2}, \dots, C_{n-2}.\] (ii) Shuffle $ C_1, \dots, C_{n-2}$ such that each car overtakes a different number of cars (i.e. $ 0, \dots, n-3$) and is overtaken by same number of cars (i.e. $ (n-3)/2$). Furthermore, we may assume $ C_{(n-1)/2}, \dots, C_{n-2}$ are still in the first $ (n-1)/2$ positions. (iii) $ A$ overtakes all other cars, including $ B$, so now it's at the front and $ B$ is at the back. (iv) $ A$ is then overtaken by the first $ (n-1)/2$ cars, which are precisely the cars $ C_{(n-1)/2}, \dots, C_{n-2}$. Final configuration of the cars: \[ B, perm(C_1, \dots, C_{(n-3)/2}), A, perm(C_{(n-1)/2}, \dots, C_{n-2})\] Note that the first $ (n-1)/2$ cars remain in the first $ (n-1)/2$ positions. To obtain a position where the first $ (n+1)/2$ cars remain in the first $ (n+1)/2$ positions, we label: \[ C_1, \dots, C_{(n-1)/2}, A, C_{(n+1)/2}, \dots, C_{n-2}, B.\] Then: (i) $ A$ is overtaken by $ C_{(n-1)/2}, \dots, C_2, C_1$ so it's now at the back. (ii) Shuffle $ C_i$'s such that the scenario holds, and $ C_{(n+1)/2}, \dots, C_{n-2}$ remain in the first $ (n-3)/2$ positions. (iii) $ A$ overtakes everyone to the front. (iv) $ B$ is overtaken by $ C_{(n+1)/2}, \dots, C_{n-2}$, not necc in order. So the final position is: \[ perm(C_1, \dots, C_{(n-1)/2}), B, perm(C_{(n+1)/2}, \dots, C_{n-2}), A\]