You can solve this in $O(n \lg n)$ time through an appropriate use of interval trees.
I'm going to explain how to process the $x$'s in an incremental, streaming fashion. So, suppose we've already received $x_1,\dots,x_n$. Define the sequence $m_1,\dots,m_n$ by $m_i=\max(x_i,x_{i+1},\dots,x_n)$. In previous processing, we'll have accumulated a data structure that summarizes the sequence $m_1,\dots,m_n$. This data structure supports two kinds of operations:
$\text{find}(\alpha)$: given a real number $\alpha$, return the largest index $i$ such that $m_i<\alpha$ but $m_{i-1}\ge \alpha$.
$\text{append}(x_{n+1})$: given the value of $x_{n+1}$, update the data structure to reflect that we've now received $x_1,\dots,x_{n+1}$. In other words, the data structure should now summarize the sequence $m'_1,\dots,m'_{n+1}$ where $m'_i = \max(x_i,x_{i+1},\dots,x_{n+1})$.
Given such a data structure, it is easy to see how to process the $x$'s in a streaming way. When we receive $x_{n+1}$, we first set $y_{n+1} = \text{find}(x_{n+1})$ and then execute $\text{append}(x_{n+1})$ to update the data structure. We iteratively repeat this for each $x$-value we receive.
I'm going to show a data structure that supports each of these two operations in $O(\lg n)$ time. This shows that we solve this problem, for the sequence $x_1,\dots,x_n$, in $O(n \lg n)$ time.
So, how do we build the data structure to represent the sequence $m_1,\dots,m_n$ and enable us to update it rapidly? We'll use an interval tree.
Consider the mapping from $\{1,2,\dots,n\} \to \mathbb{R}$ given by $i \mapsto m_i$. We want to represent this mapping efficiently. We'll do this by actually building a mapping from a set of intervals to $\mathbb{R}$, where the intervals are disjoint and their union is $\{1,2,\dots,n\}$. Whenever we have a consecutive sequence $j,j+1,\dots,k$ of indices that all map to the same value (i.e., where $m_j = m_{j+1} = \dots = m_k$), we'll collapse them into a single interval $[j,k]$. The interval tree will record the mapping $[j,k] \mapsto m_j$, which is a compact way of representing the mapping $j \mapsto m_j$, $j+1 \mapsto m_j$, $\ldots$, $k \mapsto m_j$.
Suppose we've decomposed $\{1,2,\dots,n\}$ into $k$ intervals. Our data structure will be a (balanced) binary tree with $k$ leaves, where each leaf corresponds to one of these $k$ intervals, and the leaves are in sorted order. At each internal node, we'll record the interval that covers the union of intervals at all the leaves underneath that node. Also, at each leaf, we'll record the corresponding value of $m$ (e.g., at the leaf for $[j,k]$, we'll record the value of $m_j$, which is of course the same as the value for $m_{j+1}$ and $\ldots$ and $m_k$). At each internal node, we'll record the minimal and maximum values of $m$ at all of the leaves underneath that node. This forms a binary search tree on intervals, where the search key at a node is the minimum $m$-value for the subtree rooted at that node. Since the intervals are disjoint, everything is nice and clean.
Notice that the $m_i$'s are in decreasing order, i.e., $m_1\ge m_2 \ge \dots \ge m_n$. This will help us implement both operations that the data structure needs to support. In particular, we can think of the search key at a node as the index of the left endpoint of the interval covered by the subtree rooted at that node, or we can think of the search key as the maximum $m$-value for the subtree rooted at that node.
To implement $\text{find}(\alpha)$, it's easy to traverse the tree to find the rightmost interval whose $m$-value is smaller than $\alpha$. Return the index $i$ of the left endpoint of this interval. This operation can be implemented in $O(\lg n)$ time, since we only need to traverse the search tree from the root down to an appropriate leaf.
To implement $\text{append}(x_{n+1})$, we find the rightmost interval whose $m$-value is smaller than $x_{n+1}$ and let $i$ be the left endpoint of this interval. Then, we delete this interval and every interval to its right from the interval tree. Next, we add the interval $[i,n+1]$ to the interval tree, with $m$-value $x_{n+1}$. Each of these steps can be done in $O(\lg n)$ time, so this operation can also be implemented in $O(\lg n)$ time.
