H. Сумма медиан

Числа приходят по одному. После каждого нового числа вычисляется медиана всех пришедших: при чётном количестве — меньшая из двух средних.

Выведите сумму всех $n$ медиан.

Первая строка содержит число $n$ ($1 \le n \le 10^5$).

Вторая строка содержит $n$ целых чисел, по модулю не превосходящих $10^9$.

Одно число — сумма медиан. В 32 бита она не помещается.