Finding a (Small-Big-Medium) subsequence
Your algorithm is wrong in the detail of finding a local maximum after $m$ as pointed out in the comments. 

Divide-and-conquer can be used to solve this problem. If such $i_1,i_2,i_3$ exist, there are four cases:


$i_1,i_2,i_3\le n/2$, or
$i_1,i_2\le n/2$ and $i_3&gt;n/2$, or
$i_1\le n/2$ and $i_2,i_3&gt;n/2$, or
$i_1,i_2,i_3&gt; n/2$.


Cases 1 and 4 can be checked by solving the sub-problems on $(x_1,\ldots,x_{n/2})$ and $(x_{n/2+1},\ldots,x_n)$. For other cases, numbers less than $\min_{i\le n/2} x_i$ are useless, so we can filter them in $O(n)$ time first. In the following analysis, we assume all numbers are no less than $\min_{i\le n/2} x_i$.

For case 3, $i_1$ can be adjusted to $\arg\min_{i\le n/2} x_i$, then $i_2$ and $i_3$ exist if and only if $x_{n/2+1}&lt;\cdots&lt;x_{n/2}$ does not hold. Therefore we can also check this case in $O(n)$ time.

For case 2, since we have passed case 3, we can assume $x_{n/2+1}&lt;\cdots&lt;x_{n/2}$. Let $r_1=n/2$, and $r_{i+1}$ be the largest index smaller than $r_i$ such that $x_{r_{i+1}}&gt;x_{r_i}$. Similarly let $l_1=1$, and $l_{i+1}$ be the smallest index larger than $l_i$ such that $x_{l_{i+1}}&lt;x_{l_i}$. We mark each element with which sequence its index belongs to. This can be done in $O(n)$ time and space. Easy to see $i_1$ and $i_2$ can be adjusted to $l_s$ and $r_t$ respectively for some $s$ and $t$. Furthermore, we can adjust them such that no $l_j$ or $r_j$ lies between $l_s$ and $r_t$. So we can scan from $x_1$ to $x_{n/2}$ once to get all possible $(i_1,i_2)$ pairs in $O(n)$ time. 

For example, suppose $(x_1,\ldots,x_{n/2})=(40,60,30,10,50,20)$, then
$\{r_i\}$: $6,5,2$, and $\{l_i\}$: $1,3,4$. We mark these elements as $40_l,60_r,30_l,10_l,50_r,20_r$. Possible $(i_1,i_2)$ pairs are $(40,60)$ and $(10,50)$.

Every possible $(i_1,i_2)$ pair is an open interval. We need to determine whether any of $x_{n/2+1},\ldots,x_n$ falls into these intervals. Note $x_{n/2+1},\ldots,x_n$ are sorted and so are these intervals, we can determine it in $O(n)$ time.

Now checking for case 2 and 3 costs $O(n)$ time and space, so this algorithm costs $O(n\log n)$ time and space in total.