In the city of Shanghai, the young programmer Kai seeks the wisdom of his mentor, Master Wei. One day, Master Wei presented Kai with a challenge on algorithm analysis, a fundamental lesson to achieve mastery.

"Little Kai," said the Master, "a programmer's strength lies not in writing code, but in understanding it deeply. Observe this scroll. It describes the 'Wise Partitioning Method', a way of sorting sequences."

On the scroll was an algorithm, which coincidentally looks very much like an implementation of Quicksort in Python:

cmps = 0
def quicksort(A, l, r):
    if r <= l:
        return
    # The Master chooses the middle element as a guide
    m = (l + r) // 2
    k = pivot(A, l, r, A[m])
    quicksort(A, l, k - 1)
    quicksort(A, k + 1, r)


def pivot(A, l, r, x):
    # Each element is compared with the guide x
    for y in A[l : r + 1]:
        cmps += 1
        if y < x:
            A[l] = y
            l += 1
        elif y > x:
            A[r] = y
            r -= 1
    A[l] = x
    return l

The function $$$pivot(A,l,r,x)$$$ rearranges the values in the segment $$$A[l..r]$$$ as follows: values smaller than $$$x$$$ are moved to $$$A[l..k-1]$$$ (in the same relative order), values larger than $$$x$$$ are moved to $$$A[k+1..r]$$$ (in the reverse relative order), and the guide value $$$x$$$ is placed at $$$A[k]$$$.

Master Wei then handed Kai a sequence of numbers representing the energy levels of a sleeping dragon. "A hasty apprentice would try to run this code to get the answer. But a true master can predict the cost without executing a single line."

"Your task, Kai," the Master concluded, "is to tell me the exact cost of the method for this sequence. Calculate the final value of the cost variable $$$cmps$$$ that would be obtained at the end of the $$$quicksort(A, 0, n-1)$$$ call. This is your lesson for today."