Numero di scambi eseguiti da Heapify

Data un'heap inizialmente vuota, devi eseguire q query. Esistono 2 tipi di query:

1. add x – inserisce x nell'heap

2. pop – rimuove la radice dell'heap

Per ciascuna query, devi stampare il numero di scambi necessari a ristrutturare l’heap in modo che soddisfi la proprietà del max-heap.

Nel caso delle operazioni pop, anche lo scambio tra la radice e l'ultimo elemento viene conteggiato come uno scambio.

Input

La prima riga dell'input contiene un singolo intero q (1 ≤ q ≤ ).

Le successive q righe contengono le query, una per riga. È garantito che per tutte le query add il valore di x non superi in valore assoluto.

Output

Il programma deve stampare, riga per riga, il numero di scambi eseguiti in risposta a ogni query.

Examples