Перестановкой длины \(n\) называется последовательность целых чисел от \(1\) до \(n\) длины \(n\), содержащая каждое число ровно один раз. Например, \([1]\), \([4, 3, 5, 1, 2]\), \([3, 2, 1]\) являются перестановками, а \([1, 1]\), \([0, 1]\), \([2, 2, 1, 4]\) — нет.
Была задана перестановка \(p[1 \dots n]\). Она была слита сама с собой. Другими словами, были взяты две копии \(p\) и элементы второй копии \(p\) были вставлены в первую без изменения относительного порядка элементов. Результатом является последовательность длины \(2n\).
Например, если \(p=[3, 1, 2]\), то некоторыми возможными результатами являются: \([3, 1, 2, 3, 1, 2]\), \([3, 3, 1, 1, 2, 2]\), \([3, 1, 3, 1, 2, 2]\). Следующие последовательности не являются возможными результатами слияния: \([1, 3, 2, 1, 2, 3\)], [\(3, 1, 2, 3, 2, 1]\), \([3, 3, 1, 2, 2, 1]\).
Например, если \(p=[2, 1]\), то возможными результатами являются: \([2, 2, 1, 1]\), \([2, 1, 2, 1]\). Следующие последовательности не являются возможными результатами слияния: \([1, 1, 2, 2\)], [\(2, 1, 1, 2]\), \([1, 2, 2, 1]\).
Ваша задача — восстановить перестановку \(p\) по заданной результирующий последовательности \(a\). Гарантируется, что ответ существует и единственен.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.