We will sort the prefix $p[0], p[1], \ldots, p[i-1]$ incrementally, and at each step insert $p[i]$. (We temporarily ignore $p[i+1], p[i+2], \ldots, p[n-1]$.)

Assume $p[0], p[1], \ldots, p[i-1]$ are already sorted. We can insert $p[i]$ if we know the number of indices $j < i$ such that $p[j] > p[i]$.

Divide the permutation into three parts:

• $A = (p[0], p[1], \ldots, p[i-1])$,
• $B = (p[i])$,
• $C = (p[i+1], p[i+2], \ldots, p[n-1])$.

Let: $x = \text{publish}(ABC)$, $y = \text{publish}(BAC)$,

where $ABC$ means concatenating $A$, then $B$, then $C$.

Define:

• $\text{inv}(A)$: the number of inversions inside $A$.
• $\text{inv}(A \times B)$: the number of pairs $(a,b)$ with $a \in A$, $b \in B$, and $a > b$.

Then: $$ x = \text{inv}(A)+\text{inv}(B)+\text{inv}(C)+\text{inv}(A \times B)+\text{inv}(A \times C)+\text{inv}(B \times C), $$ $$ y = \text{inv}(A)+\text{inv}(B)+\text{inv}(C)+\text{inv}(B \times A)+\text{inv}(A \times C)+\text{inv}(B \times C). $$

Subtracting: $$ x - y = \text{inv}(A \times B) - \text{inv}(B \times A). $$

Now observe: $$ \text{inv}(A \times B) = |A|\cdot|B| - \text{inv}(B \times A). $$ Since $|B|=1$, this lets us determine $\text{inv}(A \times B)$ from $x-y$, leading to a solution in $2N$ queries.

To obtain full score, we further observe that we can maintain $x$ after inserting $p[i]$ into the prefix. Specifically, after each insertion we update $x$ by subtracting $\text{inv}(A \times B)$. This saves $N$ queries, so the total number of queries becomes exactly $N$.