Qara qutu
Qara Qutu sadə bir verilənlər bazasıdır və tam ədədlərdən ibarət bir massiv saxlaya bilir. Bundan əlavə, xüsusi bir i dəyişəni mövcuddur. Başlanğıcda, Qara Qutu boşdur və i dəyişəni 0-a bərabərdir. Qara Qutu iki növ əməliyyatı emal edir:
ADD(x): elementi x Qara Qutuya əlavə edir;
GET: i-ni 1 artırır və Qara Qutuda olan bütün ədədlər arasında i-ci minimal elementi çıxarır.
Unutmayın ki, i-ci minimal element, Qara Qutunun bütün elementləri artan qaydada sıralandıqdan sonra i-ci yerdə yerləşir.
Qara Qutunun işini bir nümunə üzərində nəzərdən keçirək:
Verilmiş əməliyyat ardıcıllığını effektiv şəkildə yerinə yetirən bir alqoritm hazırlamaq lazımdır. Maksimum ADD və GET əməliyyatlarının sayı hər biri üçün 30000-dir.
Əməliyyat ardıcıllığını iki tam ədədlər massivləri ilə təsvir edək:
1. A(1), A(2), ..., A(m): Qara Qutuya əlavə olunacaq elementlərin ardıcıllığı. Elementlər modulu 2 000 000 000-dən böyük olmayan tam ədədlərdir, m ≤ 30000. Yuxarıda göstərilən nümunə üçün A = (3, 1, -4, 2, 8, -1000, 2).
2. u(1), u(2), ..., u(n): ardıcıllıq, GET əməliyyatının birinci, ikinci, ... n-ci icrası zamanı Qara Qutuda olan elementlərin sayını göstərir. Yuxarıda təsvir olunan nümunə üçün u = (1, 2, 6, 6).
Qara Qutunun işi, u(1), u(2), ..., u(n) ardıcıllığının artan qaydada sıralandığını, n ≤ m olduğunu və hər bir p üçün (1 ≤ p ≤ n) p ≤ u(p) ≤ m bərabərsizliyinin yerinə yetirildiyini nəzərdə tutur. Bu, u ardıcıllığının p-ci elementi üçün GET əməliyyatını icra edərək A(1), A(2), ..., A(u(p)) ədədlər dəstindən p-ci minimal elementi çıxarmaqla nəticələnir.
Giriş verilənləri
Giriş aşağıdakı ədədlər dəstindən ibarətdir: m, n, A(1), A(2), ..., A(m), u(1), u(2), ..., u(n). Bütün ədədlər boşluqlar və (və ya) yeni sətir simvolu ilə ayrılır.
Çıxış verilənləri
Qara Qutunun icra edilmiş əməliyyatlar ardıcıllığına verdiyi cavabları çıxarın. Hər bir ədədi ayrıca sətirdə çıxarmaq lazımdır.