Minimum interval dəyəri
Şirkət Giggle Sudislavlda yeni ofisini açır və siz müsahibəyə dəvət olunmusunuz. Sizin vəzifəniz verilmiş tapşırığı həll etməkdir.
Sizdən tam ədədlərdən ibarət bir verilənlər strukturu yaratmaq tələb olunur. Əvvəlcə massiv boşdur. Siz iki əməliyyatı dəstəkləməlisiniz:
sorğu: "? i j" - i-ci və j-ci elementlər arasında, daxil olmaqla, minimum elementi qaytarır;
dəyişiklik: "+ i x" - i-ci elementdən sonra x elementini əlavə edir. Əgər i = 0 olarsa, element massivə başlanğıcda əlavə olunur.
Əlbəttə ki, bu struktur kifayət qədər yaxşı olmalıdır.
Giriş məlumatları
Birinci sətir massiv üzərində əməliyyatların sayını n (1 ≤ n ≤ 200000) ehtiva edir. Növbəti n sətir əməliyyatların özünü təsvir edir. Bütün əlavə əməliyyatları düzgün şəkildə verilmişdir. Massivdə saxlanılan bütün ədədlər modulu ilə 10^9-u keçmir.
Çıxış məlumatları
Hər bir ? əməliyyatı üçün ayrı sətirdə onun nəticəsini çıxarın.