Как найти 3 числа в порядке возрастания и увеличения индексов в массиве за линейное время

Я наткнулся на этот вопрос на веб-сайте. Как упоминалось там, это было задано в интервью Amazon. Я не мог найти правильное решение в данном ограничении.

Учитывая массив из nцелых чисел, найдите 3 элементатакие, что a[i] < a[j] < a[k]и i < j < kза O(n)раз.