G. Очередь на минимум

Та же приоритетная очередь, что в классе, но извлекается минимум, а не максимум.

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

Формат ответов не меняется: на извлечение - индекс, куда уехал бывший последний элемент (или 0, если элемент был единственным), и само значение; на добавление - индекс или $-1$ при переполнении.

Всё, что нужно поменять, - два знака сравнения. Но менять надо оба и в правильную сторону: в просеивании вниз выбирается наименьший из детей, а условие обмена становится a[best] < a[i].

Проверьте себя на очереди вместимости 2 и запросах «добавить 5», «добавить 5»: второй должен вернуть индекс 2, а не поменять элементы местами.

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

Далее $M$ строк. Тип 1 - извлечь минимум. Тип 2 - добавить число из $[-10^9; 10^9]$.

Ответ на каждый запрос по правилам выше.

После всех запросов - строка с кучей в конечном состоянии.