$count = 0
def merge(left_array, right_array)
  return_array = []
  left_index, right_index = 0, 0
  left_array << -1
  right_array << -1
  0.upto(left_array.length + right_array.length - 3) do
    $count += 1
    if left_array[left_index] > right_array[right_index]
      return_array << left_array[left_index]
      left_index += 1
    else
      return_array << right_array[right_index]
      right_index += 1
    end
  end
  return_array
end

def merge_sort(target_array)
  right = target_array.length
  mid = target_array.length / 2
  left_array = target_array[0...mid]
  right_array = target_array[mid...right]
  return target_array if target_array.length == 1
  return merge(merge_sort(left_array), merge_sort(right_array))
end

gets.to_i
input = gets.split(' ').map(&:to_i)
merge_sort input
puts $count
