Finding a (Small-Big-Medium) subsequence

Question

Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{i_3}<x_{i_2}$. Only a yes-no answer is required.

The statement also suggest to use the "divide & conquer" strategy.

My try was the following:

I read the vector left to right

• If the list changes from increasing to decreasing, then it is clear that the last read number is lower than the maximum of the currently read list. So if it is greater than the minimum of the current list we can stop. This comparation can be done in $\mathcal{O}(1)$ if we keep track of the minimum of the currently read list.
• If the list changes from decreasing to increasing, then I look for the first number $m$ in the list which is a local minimum and it is lower than the last read number $c$. And then I look for a local maximum appearing after $m$ which is greater than $c$. If both searches are successful we can end. This searches can be done in $\mathcal{O}(\log n)$ time if we keep track of the local maximums and local minimums currently found (binary search).
• If the list keeps increasing we do the same as in the previous step.
• If the list keeps decreasing do nothing.

So the complexity is $\mathcal{O}(n\log n)$. I think the strategy is good, but an online judge rejected it. I don't know if it is due to a silly bug or because the strategy is indeed wrong.

Anyway, seeing the stats of the people who solved the problem, my solution is so memory consumming, so I really think it can be done better.

Any idea?