Masala #0967

Xotira 512 MB Vaqt 2000 ms Qiyinchiligi 53 %
3.6 (Baholar 9)
14

  

Eeeelffff

Qorboboda sovg'a ulashishi kerak bo'lgan N ta bolaning ro'yxati bor edi. Qorbobo bu ro'yxatni ko'zdan kechirar ekan ro'yxat N o'lchamdagi P permutatsiya ekanligini tushunib qoldi. Qorbobo sovg'alarni ro'yxatdagi tartibda ulashishga qaror qildi va permutatsiyani yordamchi elfga saqlash uchun berdi.

Elf bekorchi vaqtida P permutatsiyadan foydalanib A massivini yasadi. Har bir AiA_i (1iN)(1\leq i \leq N) ning qiymati ii son uchun P permutatsiyada ii sondan o'ng tarafdagi o'zidan katta eng yaqin sonning qiymatini, agar bunday son mavjud bo'lmasa -1 qiymatni saqlaydi. Yaxshiroq tushunish uchun izohga qarang!

Lekin elf A massivni yasash uchun P permutatsiyani bo'yab tashladi. Endi u Qorbobodan gap eshitmasligi uchun permutatsiyani qayta tiklashi kerak. Elfga yordam bera olasizmi ?


Kiruvchi ma'lumotlar:

Birinchi qatorda N (1N2105)(1 \leq N \leq 2*10^{5}) natural son kiritiladi.
Ikkinchi qatorda N ta sondan iborat A massiv kiritiladi.


Chiquvchi ma'lumotlar:

N uzunlikdagi P permutatsiyani chiqaring.


Misollar
# input.txt output.txt
1
3
-1 3 -1
2 3 1
2
3
3 -1 -1
1 3 2
Izoh:

P={2,3,1}
1 soni uchun o'zidan o'ng tarafda 1 dan katta son yo'q, demak A1=1;A_1=-1;
2 soni uchun o'zidan o'ng tarafda 2 dan katta 3 soni mavjud, demak A2=3;A_2=3;
3 soni uchun o'zidan o'ng tarafda 3 dan katta son yo'q, demak A3=1.A_3=-1.
A={-1,3,-1}.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin