Количество обменов (swaps), выполняемых при Heapify

Дана изначально пустая куча (heap). Требуется обработать q запросов. Запросы бывают двух типов:

1. add x — добавляет x в кучу

2. pop — удаляет корень кучи

Для каждого запроса необходимо вывести, сколько обменов пришлось сделать для перестройки кучи и сохранения свойства max-heap.

Обратите внимание, что в операции pop обмен корня с последним элементом также считается за один обмен.

Входные данные

Первая строка содержит одно целое число q (1 ≤ q ≤ ).

Следующие q строк содержат запросы — по одному в каждой строке. Гарантируется, что при любом запросе add значение x не превосходит по модулю .

Выходные данные

Программа должна вывести количество операций обмена, по одной на строку.

Пример