Finding a Friend's Name

Let the missing student's name be $x$.

If $n>1$, the student immediately before $x$ in Class 6 must be $a_{n-1}$, so $a_{n-1}<x$. If $n<m$, the student immediately after $x$ must be $a_n$, so $x<a_n$.

Therefore, for each name $x$, it is sufficient to check the following two conditions:

• If $n>1$, then $a_{n-1}<x$.
• If $n<m$, then $x<a_n$.

The complete second-grade roster is already sorted. Collecting valid names in input order automatically produces the required sorted output.

The time complexity is $O(m+k)$ per test case, and the space complexity is $O(k)$ when the candidates are stored.

Solution written by GPT5.6