Given the array ~a~ of length ~n~, define ~P(i, j)~ to be the probability that ~a_i~ and ~a_j~ form an inversion (~i < j~, ~a_i > a_j~). For a pair ~(i, j)~, ~P(i, j)~ is defined to be ~\frac{1}{2}~, since there are two cases; ~a_i > a_j~ and ~a_i < a_j~.

Using linearity of expectation, the expected number of inversions of the permutation is defined as:

$$\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n P(i, j) = \binom{n}{2} P(i, j) = \frac{n(n-1)}{4}$$

In this problem, since there are prefilled positions in our array, there are ~3~ cases to be considered:

Case 1:

• For all ~i~, where ~a_i \neq 0~ we can calculate the number of inversions directly using any range tree.

Case 2:

• Considering all pairs ~(i, j)~ where ~a_i, a_j = 0~, we define ~\sum P(i, j) = \frac{len(len - 1)}{4}~ where ~len~ is the number of positions ~i~ such that ~a_i = 0~.

Case 3:

• Considering pairs ~(i, j)~ where one of ~a_i, a_j~ is ~0~, more careful calculation is required. We define two sets ~\mathbb{S}~ and ~\mathbb{T}~ where ~\mathbb{S}~ is the set of all positions ~i~ such that ~a_i \neq 0~, and ~\mathbb{T}~ holds all positions ~i~ where ~a_i = 0~.

• Start by looping through all indices in ~\mathbb{S}~. We seek to calculate ~\sum_{j \in \mathbb{T}} P(i, j)~. For each ~i~, consider two cases where ~j < i~ and ~j > i~.

  • Let ~\mathbb{T}_\text{small}~ be the set ~\{x \in T \mid x < a_i\}~, and Let ~\mathbb{T}_\text{big}~ be the set ~\{x \in T \mid x > a_i\}~.

  • For ~j < i~, the probability ~P(i, j)~ is defined as: ~\frac{n(\mathbb{T}_\text{big})}{n(\mathbb{T})}~. This is since a larger integer should be placed before ~a_i~, to create an inversion.

  • Likewise for ~j > i~, the probability ~P(i, j)~ is defined as: ~\frac{n(\mathbb{T}_\text{small})}{n(\mathbb{T})}~, and this time ~a_i~ should be larger than the integer placed at ~a_j~ to create an inversion.

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