The first subtask is very similar to the classic inversion counting problem.

For every ~i~, the number of new inversions is equal to the number of ~j < i~ where ~a_j < a_i~. This can be found in ~\mathcal O(N \log N)~ time by using a range tree.

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

For the second subtask, we can maintain a range tree to count the number of 1's in a given range, and a second range tree to count the number of 2's in a given range.

If ~a_{p_i} = 1~, then the number of new inversions is the number of ~j < p_i~ such that ~a_j = 2~. If ~a_{p_i} = 2~, then the number of new inversions is the number of ~j > p_i~ such that ~a_j = 1~.

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

For the final subtask, we note that we can represent every value with the tuple ~(p_i, a_i, i)~.

One solution is to sort all of the points by their ~p_i~ values. The number of new inversions equals the number of points where ~p_j < p_i~, and either ~a_i < a_j \land j < i~ or ~a_i > a_j \land j > i~.

A memory-optimized 2D data structure can solve this in ~\mathcal O(N \log^2 N)~.

Alternatively, we can use divide and conquer with a 1D range tree, which also yields an ~\mathcal O(N \log^2 N)~ solution.

Time Complexity: ~\mathcal O(N \log^2 N)~