Növbəti
Verilənlər strukturunu həyata keçirin ki, bu struktur tam ədədlərdən ibarət S çoxluğunu dəstəkləsin və aşağıdakı əməliyyatları icra etməyə imkan versin:
add(i) – S çoxluğuna i ədədini əlavə edin (əgər artıq oradadırsa, çoxluq dəyişməz);
next(i) – çoxluğun i-dən kiçik olmayan ən kiçik elementini qaytarın. Əgər belə bir element struktura daxil deyilsə, –1 qaytarın.
Giriş verilənləri
Başlanğıcda S çoxluğu boşdur. Giriş faylının ilk sətiri n əməliyyatların sayını göstərir (1 ≤ n ≤ 300 000). Növbəti n sətir əməliyyatları təsvir edir. Hər bir əməliyyat ya "+ i", ya da "? i" formasındadır. "? i" əməliyyatı next(i) sorğusunu ifadə edir.
Əgər "+ i" əməliyyatı giriş faylında əvvəlcə və ya başqa "+" əməliyyatından sonra gəlirsə, bu add(i) əməliyyatını ifadə edir. Əgər sorğudan sonra "?" və bu sorğunun nəticəsi y olarsa, add((i+y) mod 10^9) əməliyyatı icra edilir.
Bütün sorğularda və əlavə əməliyyatlarında parametrlər 0 ilə 10^9 arasında yerləşir.
Çıxış verilənləri
Hər bir sorğu üçün bir ədəd çıxarın – sorğunun cavabı.