It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid sequence with indices in $[t]$ and the best valid sequence which ends with $A[t]$. At time $t+1$ we update $\mathbf{X}_t$ and $\mathbf{Y}_t$ as follows. If $(\mathbf{Y}_t, A[t+1])$ is a valid sequence of length longer than $\mathbf{X}_t$, then we set

$\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$ and $\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$.

Otherwise, we set $\mathbf{X}_{t+1}:=\mathbf{X}_t$ and we can compute $\mathbf{Y}_{t+1}$ in $O(\log (n))$-time via binary search.

It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid sequence with indices in $\{1, \dots, t\}$ and the best valid sequence which ends with $A[t]$. At time $t+1$ we update $\mathbf{X}_t$ and $\mathbf{Y}_t$ as follows. If $(\mathbf{Y}_t, A[t+1])$ is a valid sequence of length longer than $\mathbf{X}_t$, then we set

$\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$ and $\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$.

Otherwise, we set $\mathbf{X}_{t+1}:=\mathbf{X}_t$ and we can compute $\mathbf{Y}_{t+1}$ in $O(\log (n))$-time via binary search.