Heapify-ի արդյունքում կատարվող փոխանակումների քանակը
Սկզբում տրված է դատարկ heap (կույտ), և ձեզ խնդրում են կատարել
q հարցում (query): Հարցումները երկու տեսակ են.add x- պետք է ավելացնիx-ը heap-ի մեջ
pop- պետք է ջնջի heap-ի հիմքը (root)
Հարցումներից յուրաքանչյուրի համար անհրաժեշտ է տպել այն փոխանակումների քանակը, որը պահանջվում է heap-ը վերակառուցելու համար, որպեսզի այն բավարարի max-heap-ի հատկությունները:
Նշենք, որ
pop գործողության դեպքում root-ի և վերջին էլեմենտի փոխանակումը նույնպես դիտարկվում է որպես swap:Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ число
q (1 ≤ q ≤ ):Հաջորդ
q տողերում տրված են հարցումները՝ ամեն մեկը առանձին տողում։ Համոզված եղեք, որ բոլոր add հարցումների դեպքում x-ի մեծությունը չի գերազանցի -ը բացարձակ արժեքով:Ելք
Ծրագիրը պետք է տպի փոխանակումների քանակը ամեն հարցման համար առանձին տողով:
Օրինակներ
Մուտք | Ելք |
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