Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?
This is variation of Longest increasing subsequence problem; this is the solution presented on Wikipedia using two auxiliary arrays $M$ and $P$:


  
  $M[j]$ — stores the position $k$ of the smallest value $A[k]$ such that there is an increasing subsequence of length $j$ ending at $A[k]$ on the
  range $k \leq i$ (note we have $j \leq k \leq i$ here, because $j$ represents the
  length of the increasing subsequence, and $k$ represents the position of
  its termination. Obviously, we can never have an increasing
  subsequence of length $13$ ending at position $11$. $k \leq i$ by definition).
  $P[k]$ — stores the position of the predecessor of $A[k]$ in the longest increasing subsequence ending at $A[k]$.
  
  In addition the algorithm stores a variable $L$ representing the length
  of the longest increasing subsequence found so far.
  


This algorithm runs in worst-case time $\Theta(n\log n)$. Your problem is a special case that allows you to return when $L=3$ which pushes runtime down to $O(n)$ because the binary search runs only on arrays of length at most two, which is therefore in time $O(1)$ as opposed to $\Theta(\log n)$ in the general case.

Consider the modified pseudo code:

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] &lt; X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] &lt; X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
   if L==3 : return true; // you can break here, and return true.
return false; // because L is smaller than 3.