Nombre d’échanges effectués par Heapify

Étant donné qu’au départ le tas (heap) est vide, vous devez exécuter q requêtes. Il existe 2 types de requêtes :

1. add x – doit ajouter x au tas

2. pop – doit supprimer la racine du tas

Pour chacune de ces requêtes, vous devez afficher le nombre d’échanges nécessaires afin de réorganiser le tas pour qu’il respecte la propriété de max-heap (tas maximum).

Pour les opérations pop, l’échange entre la racine et le dernier élément est également comptabilisé comme un échange.

Input

La première ligne de l’entrée contient un entier q (1 ≤ q ≤ ).

Les q lignes suivantes contiennent les requêtes, chacune sur sa propre ligne. Il est garanti que, pour toutes les requêtes add, la valeur de x ne dépasse pas en valeur absolue.

Output

Le programme doit imprimer le nombre d’opérations d’échange, chacune sur une nouvelle ligne.

Examples