Masala #0186

Xotira 32 MB Vaqt 2000 ms Qiyinchiligi 60 %
14

  

Oraliqlar daraxti

Azimjon N ta har xil elementdan iborat(qiymatlari takrorlanmaydigan) A massiv uchun 2×N-1 ta elementdan iborat T oraliqlar daraxti orqali minimum qiymatni hisoblash uchun quyidagi tartibda tuzdi:

for i in range(0, N): T[i+N-1] = A[i]

for i in range(N-2, -1, -1): T[i] = min(T[i*2+1], T[i*2+2])

Shundan so’ng o’zining A massivini tashlab yubordi va o’ziga 2×N-1 ta elementdan iborat T massivni saqlab qoldi. Azimjon uyda yo’qligidan foydalanib uning ukasi Azimjonning T massiv elementlarini qiymatlarini tartibini almashtirib qo’ydi, va hattoki ba’zi elementlarining qiymatini o’zgartirib ham qo’ygan bo’lishi mumkin. Bundan xabar topgan Azimjon o’zining T massivini qiymatlari almashgan bo’lsada yuqoridagi qonuniyatiga mos keladigan holda qayta tiklamoqchi bo’ldi. Qayta tiklaganida ham A massivga mos keladigan elementlar unikal(yagona)ligini saqlab qolishi kerak. Sizning vazifangiz Azimjon buni eplay oladimi yoki yo’qligini aniqlashdan iborat.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida N=2k shaklidagi bitta butun son, N(1 ≤ N ≤ 218) soni kiritiladi. Keyingi satrda 2×N-1 ta son, Azimjonning ukasidan qolgan T(-109 ≤ Ti ≤ 109) massivining elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida agar Azimjon o’z massivini qayta tiklay olsa dastlabki satrda YES so’zini, keyingi satrda esa 2×N-1 ta elementdan iborat T massivining qayta tiklangan holatini (Agar yechimlar ko’p bo’ladigan bo’lsa leksikografik eng kichigini) chop eting, agar qayta tiklay olmasa yagona satrda NO so’zini chop eting.


Misollar
# input.txt output.txt
1
4
3 1 3 1 2 4 1
YES
1 1 3 1 2 3 4 
2
2
1 1 1
NO
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin