E. Извлечение максимального

Дана куча размера $N > 1$. Выполните $N - 1$ извлечений максимума.

Процедура фиксирована: последний элемент кучи помещается в корень, размер уменьшается на единицу, затем корень просеивается вниз. После каждого извлечения выведите, на каком индексе остановился просеиваемый элемент, и какое значение было извлечено.

В первой строке - размер кучи $N$ ($2 \le N \le 10^5$).

Во второй - сама куча: $N$ различных целых чисел из $[-10^9; 10^9]$.

Выведите $N - 1$ строк, в каждой два числа: индекс, на котором остановился просеиваемый элемент, и значение извлечённого максимума.