You have integer array of length n ([1 2 1 2 1 3 1 3]).Remove all occurance of 1(array become [2 2 3 3]).Now you can append this resulting array to initial array , any number of time ([1 2 1 2 1 3 1 3 2 2 3 3]).

Given a resulting array print the initial array

eg.

input

1 2 1 2 1 3 1 3 2 2 3 3 2 2 3 3

output:

1 2 1 2 1 3 1 3

if no initial array possible print -1

if multiple ans possible print lexicographically smaller array.

Find the prime factorisation of N , Where N = size of the resulting array - No. Of 1’s in resulting array .

Let cnt be no. of 1’s in resultant array.

Let array B be an array which is resulting array - all occurence of 1’s.

Let last be the position of the last 1 in resulting array.

There can be atmost log(N) prime factors of N . Check that whether they can make the resultant array after repeating themselves if they do then insert them in set S. Now , the final length of array would be smallest no. >= Last - cnt ( let it be Y ), which is completely divisible by elements present in set S.

Now , just print prefix of resulting array of size Y+cnt.

Alternate solution can be of O(N*sqrt(N)) . Where we find the smallest factor of N >= last - cnt , which makes array B by repeating itself .