One Change Sorting

Given a sequence of integers \(a_1, a_2, \ldots, a_n\), determine if it is possible to obtain a non-decreasing sequence by modifying at most one element. If it is possible, output the modified sequence; otherwise, output -1.

You are allowed to change one integer in the sequence to any other integer such that the resulting array is sorted in non-decreasing order. Formally, a sequence \(a_1, a_2, \ldots, a_n\) is non-decreasing if \(a_i \le a_{i+1}\) for all \(1 \le i < n\). If the sequence is already non-decreasing, simply output the sequence as is.

Examples:

• For n = 5 and sequence = [1, 2, 10, 5, 6], one valid solution is to change 10 to 5, resulting in [1, 2, 5, 5, 6].
• For n = 3 and sequence = [4, 1, 3], one valid solution is to change 4 to 1, resulting in [1, 1, 3].
• For n = 4 and sequence = [5, 4, 3, 2], it is not possible to fix the sequence by changing only one element, so output -1.

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)) representing the number of elements in the sequence.

The second line contains n space-separated integers representing the sequence.

outputFormat

If the sequence can be made non-decreasing by modifying at most one element, output the modified sequence as n space-separated integers on a single line. Otherwise, output -1.

## sample

5
1 2 10 5 6

1 2 5 5 6

</p>