C. Сколько стоит построение

Постройте кучу из массива тем же алгоритмом, что в классе - просеиванием вниз по индексам от $\lfloor N/2 \rfloor$ до 1, - и выведите суммарное количество обменов.

Это способ увидеть линейность построения своими глазами. Теория обещает, что суммарная работа не превосходит $N$; посмотрите, сколько получается на самом деле.

На отсортированном по возрастанию массиве обменов будет много - почти каждый элемент придётся опускать. На отсортированном по убыванию массив уже является кучей, и обменов не будет вовсе. Оба теста в наборе есть.

Сравните полученное число с $N \log_2 N$: разница между линейным построением и построением вставками видна сразу.

В первой строке - число $N$ ($1 \le N \le 10^5$).

Во второй - $N$ целых чисел, по модулю не превосходящих $10^9$. Числа могут повторяться.

Одно число - суммарное количество обменов при построении.