Numero di scambi eseguiti da Heapify
Data un'heap inizialmente vuota, devi eseguire
q query. Esistono 2 tipi di query:add x– inseriscexnell'heap
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
Input | Output |
7
add 1
add 2
add -3
add 4
pop
add -2
pop | 0
1
0
2
2
0
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB