لدى أليس وبوب $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$ |