Masala #0967

Xotira 512 MB Vaqt 2000 ms
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 \(A_i\) \((1\leq i \leq N)\) ning qiymati \(i\) son uchun P permutatsiyada \(i\) 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 \((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 \(A_1=-1;\)
2 soni uchun o'zidan o'ng tarafda 2 dan katta 3 soni mavjud, demak \(A_2=3;\)
3 soni uchun o'zidan o'ng tarafda 3 dan katta son yo'q, demak \(A_3=-1.\)
A={-1,3,-1}.