Lemma: If we have no information about the relative values of person ~i~ and person ~j~, we must query for which of the two did better.

Proof: We can take any consistent ranklist where we have no relative information for these two individuals and collapse it into one where person ~i~ and person ~j~ are adjacent. If person ~k~ is between person ~i~ and person ~j~, it cannot be the case that person ~k~ is forced to be between them, because that would imply the relative standing of person ~i~ and person ~j~. Since person ~k~ is not forced to be between them, we can move them to be either above both individuals or below both individuals.

Now, given that we have a consistent ranklist and person ~i~ and ~j~ are adjacent, we can also swap them, since we are not forced to compare them. However, this means we have two ranklists that are consistent, which is in violation of the ranklist needing to be unique.

Therefore, we are required to do a relative comparison of every individual.

Consequently, it suffices to compute, for each pair of individuals, whether we know anything about their relative order. If we construct a graph where there's a directed edge from ~i~ to ~j~ if person ~i~ did better than person ~j~, we can compute the number of unordered pairs ~(x, y)~ where ~x~ and ~y~ are not reachable from each other in either direction. The answer is therefore the number of such pairs.

To compute the reachability quickly, we can run BFS ~N~ times or use Floyd-Warshall.