Masala #0926

Xotira 16 MB Vaqt 1000 ms
14

Massivni almashtirish

Sizga 1 dan n gacha bo'lgan sonlarning premutatsiyalaridan biri beriladi. Ya'ni \(a_n(a_1,a_2,a_3,...,a_n)\) massiv berilgan, shu massivni elementlari tartibi shunday o'zgartiring hosil bo'lgan \(b_n(b_1,b_2,b_3,...,b_n)\) massiv kiritilgan massiv bilan quyidagi shartlarni qanoatlantirsin.

  • \(a_1 \not= b_1, a_2 \not= b_2, ... ,a_n \not= b_n\)

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t(1 \leq t \leq 200)\) testlar soni va har bir testni birinchi qatorida \(n(1 \leq n \leq 1000)\) massiv uzunligi va ikkinchi qatorida \(a_1,a_2,a_3,...,a_n(1 \leq a_i \leq n)\) sonlar toplami kiritiladi.


Chiquvchi ma'lumotlar:

Hosil qilinadigan premutatsiyalar bir nechtasi shartni qanoatlantirishi mumkun, shuning uchun leksikografik jihatdan eng kichik premutasiyani chop eting. Agar bunday premutasiya mavjud bo'lmasa -1 ni chop eting.


Misollar
# input.txt output.txt
1
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
2 3 1
1 2 3 4 5
1 2 4 3
-1