Amazon | OA | (forgot the real name) sequence of x with minimum length that sorts the array

Round 1

Questions: Given an unsorted array a and x as the value of array at A[ith]. If x is picked, all other values less than x will be put on the left side, values greater than or equal to x will remain in the same position. Return the sequence of x with minimum length that sorts the array.

Example:

x = 2
a = [6, 4, 3, 5, 2, 1]
newA = [1, 6, 4, 3, 5, 2]

x = 3
a = [1, 6, 4, 3, 5, 2]
newA = [1, 2, 6, 4, 3, 5]

x = 4
a = [1, 2, 6, 4, 3, 5]
newA = [1, 2, 3, 6, 4, 5]

x = 6
a = [1, 2, 3, 6, 4, 5]
newA = [1, 2, 3, 4, 5, 6]

result = [2, 3, 4, 6]