לאליס ולבוב יש $2n$ קלפים, שעל כל אחד מהם כתוב מספר שלם, כך שכל מספר שלם בין $1$ ל-$n$ מופיע בדיוק על שני קלפים. בהתחלה, אליס ובוב מחזיקים כל אחד $n$ קלפים.
הם עומדים לשחק משחק קלפים, כאשר אליס מתחילה ראשונה. בכל תור, השחקן הנוכחי מניח קלף מידו בראש הערימה. אם יש כעת שני קלפים עם אותו מספר בערימה, השחקן הנוכחי צובר נקודה $1$ ומוציא את שני הקלפים התואמים יחד עם כל הקלפים שביניהם, ומניח אותם בערימת הקלפים שנזרקו.
בהינתן רצף המהלכים של אליס, כיצד יכול בוב לסדר את מהלכיו כדי למזער את הניקוד של אליס?
קלט
השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 10^5$), המציין את מספר מקרי הבדיקה.
עבור כל מקרה בדיקה, השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 5 \times 10^5$).
השורה השנייה מכילה $n$ מספרים שלמים $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), המייצגים את המספרים על הקלפים שאליס משחקת לפי הסדר. מובטח כי אף מספר אינו מופיע יותר מפעמיים ב-$a_i$.
מובטח כי סכום ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $5 \times 10^5$.
פלט
עבור כל מקרה בדיקה, השורה הראשונה של הפלט צריכה להכיל מספר שלם, המייצג את הניקוד המינימלי שאליס יכולה לקבל.
השורה השנייה צריכה להכיל $n$ מספרים שלמים $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), המייצגים את המהלכים של בוב לפי הסדר, כך שכל מספר שלם מ-$1$ עד $n$ מופיע בדיוק פעמיים ברצפים המשולבים של $a_i$ ו-$b_i$.
דוגמה
קלט
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
פלט
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
הערה
עבור מקרה הבדיקה השלישי, המשחק מתנהל באופן הבא:
| צעד | שחקן | קלף ששוחק | הערימה מלמטה למעלה | הניקוד של אליס | הניקוד של בוב |
|---|---|---|---|---|---|
| $1$ | אליס | $1$ | $[1]$ | $0$ | $0$ |
| $2$ | בוב | $3$ | $[1, 3]$ | $0$ | $0$ |
| $3$ | אליס | $4$ | $[1, 3, 4]$ | $0$ | $0$ |
| $4$ | בוב | $2$ | $[1, 3, 4, 2]$ | $0$ | $0$ |
| $5$ | אליס | $5$ | $[1, 3, 4, 2, 5]$ | $0$ | $0$ |
| $6$ | בוב | $2$ | $[1, 3, 4]$ | $0$ | $1$ |
| $7$ | אליס | $1$ | $[]$ | $1$ | $1$ |
| $8$ | בוב | $3$ | $[3]$ | $1$ | $1$ |
| $9$ | אליס | $4$ | $[3, 4]$ | $1$ | $1$ |
| $10$ | בוב | $5$ | $[3, 4, 5]$ | $1$ | $1$ |