Build a segment tree over the array ~A~ with the missing student inserted at the beginning. Since ~N~ is a power of 2, the structure of the segment tree is the same as the structure of a tournament, where each non-leaf node represents a match between two students. At each node of the tree, store two values: the winner of the match ~\text{mx}~ (i.e., the maximum skill of any student in the node's subtree) and the sum of the underwhelmingness of all matches played in the node's subtree, denoted as ~\text{sum}~. The segment tree must also support an update operation to modify a value in ~A~. The solution for a given array ~A~ is given by ~\text{sum}_{\text{root}}~.

To find the answer for all possible positions to insert the missing student, two update operations can be used to swap the missing student with their neighbor to the right, querying ~\text{sum}_{\text{root}}~ after each swap. This process is repeated until the answer has been found for every possible position of the missing student.

Time Complexity: ~\mathcal{O}(N\log{}N)~