import random

comparisons = 0

def getPivot(A, l, r):
    return random.choice(A[l:r+1])

def partition(A, l, r):
    global comparisons
    comparisons += (r-l)
    A[l], A[r] = A[r], A[l]
    p = A[l]
    i = l+1
    for j in range(l, r+1):
        if A[j] < p:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[l], A[i-1] = A[i-1], A[l]

    return (i-2, i)

def qsort(A, l, r):
    if l >= r:
        return
    else:
        (i,j) = partition(A, l, r)
        qsort(A, l, i)
        qsort(A, j, r)
        return


A = map(int,open('QuickSort.txt').read().split('\r\n')[:-1])
qsort(A,0,len(A)-1)
print comparisons
#print A