We maintain an array that, for each child, keeps track of the station they got off on. The query comes down to finding the first element smaller than or equal to ~Y~ in a suffix of that array. Linear search (for loop) is obviously too slow for large test cases. Therefore, we will use a tournament tree where each vertex holds the minimum of the corresponding intervals of the observed array. With each Marica's statement, we update the tree in the standard way, from the leaves to the roots.

In the query, that starts from the root of the tree, we behave in the following way:

• Call the query for the left child if its interval contains elements in common with the required suffix and if its minimum is smaller than or equal to ~Y~.
• If the query for the left child found the required element, return it.
• Otherwise, call the query for the right child and return the given element or -1 if none was found.

What is the complexity of the query? The largest number of nodes reached will be:

• the ~\mathcal O(\log N)~ nodes of the tournament tree that precisely cover the required suffix and all the nodes on the path to these, which is again ~\mathcal O(\log N)~,
• the path from the first of the nodes whose minimum is smaller than or equal to ~Y~ to one of the leaves, which is again ~\mathcal O(\log N)~.