Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Читаем входные данные
    val n = reader.readLine().toInt()
    val x = reader.readLine().split(" ").map { it.toLong() }.toLongArray()

    // Две кучи: smaller (max-heap) и larger (min-heap)
    val smaller = PriorityQueue<Long> { a, b -> b.compareTo(a) } // Max-heap
    val larger = PriorityQueue<Long>() // Min-heap

    var sum = 0L // Используем Long для суммы, так как числа до 10^9

    // Обрабатываем каждый префикс
    for (i in 0 until n) {
        val current = x[i]

        // Добавляем элемент в соответствующую кучу
        if (smaller.isEmpty() || current < smaller.peek()) {
            smaller.add(current)
        } else {
            larger.add(current)
        }

        // Балансируем кучи
        if (smaller.size > larger.size + 1) {
            larger.add(smaller.poll())
        } else if (larger.size > smaller.size) {
            smaller.add(larger.poll())
        }

        // Находим медиану и добавляем к сумме
        sum += smaller.peek()
    }

    // Выводим результат
    writer.write(sum.toString())
    writer.newLine()

    reader.close()
    writer.close()
}