По заданному массиву найдите следующий меньший элемент в массиве для каждого элемента без изменения исходного порядка элементов.

Например, предположим, что данный массив равен 4,2,1,5,3.

Результирующий массив будет 2,1, -1,3, -1.

Мне задали этот вопрос в интервью, но я не мог придумать решение лучше, чем тривиальное решение O (n ^ 2). Любой подход, который я мог бы придумать, то есть создание бинарного дерева поиска или сортировка массива, исказит исходный порядок элементов и, следовательно, приведет к неверному результату.

Любая помощь будет высоко ценится.