DoubleSort Algorithm Challenge

You are given an array of n integers. Your task is to implement the DoubleSort algorithm, which sorts the array in increasing order by value. For elements that have the same value, the element that appeared later in the original array should come before the one that appeared earlier.

More formally, given an array \(A = [a_0, a_1, \dots, a_{n-1}]\), you need to sort it so that if \(a_i = a_j\) and \(i < j\), then in the sorted array, \(a_j\) appears before \(a_i\). Otherwise, the numbers are sorted in ascending order.

Note: The tie-breaking rule effectively sorts duplicates by the original index in descending order while overall sorting is in ascending order.

inputFormat

The input is given from standard input (stdin) and is structured as follows:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of elements in the array.
• The second line contains \(n\) integers separated by spaces.

outputFormat

Print the sorted array according to the DoubleSort algorithm on a single line. The elements must be separated by a single space.

1
1

1