Counting Swaps in Quicksort

When Prof. Pang was young, he wrote the following code for quick sort. Please calculate how many swaps are performed when calling \(\textbf{quicksort}(A, 1, n)\). Here, \(A\) is a given permutation of length \(n\). The quicksort algorithm is implemented as follows:

quicksort(A, p, r):

if p < r then
    q = partition(A, p, r)
    quicksort(A, p, q-1)
    quicksort(A, q+1, r)

partition(A, p, r):

x = A[r]
i = p - 1
for j = p to r-1 do
    if A[j] \(\leq\) x then
        i = i + 1
        swap A[i] and A[j]   // count this swap
if i+1 \(\neq\) r then
    swap A[i+1] and A[r]     // count this swap
return i + 1

Note: Even if a swap exchanges an element with itself, it is still counted as a swap.

inputFormat

The first line contains an integer \(n\) (1 \(\leq\) n \(\leq\) 10⁵), denoting the length of the permutation \(A\).

The second line contains \(n\) distinct integers \(A[1], A[2], \ldots, A[n]\), which form a permutation of \(\{1, 2, \ldots, n\}\).

outputFormat

Output a single integer, the total number of swaps performed when running \(\textbf{quicksort}(A, 1, n)\).

sample

3
1 3 2

2