Hi!

I am trying to solve problem I from the 2017-2018 ACM-ICPC Central Europe Regional Contest (CERC 17) as indicated by the official solution. I understood the divide and conquer argument but it's not clear how to compute the left intervals and the right intervals in O(hi — lo). Basically, I cannot understand how this step in the solution works: "Starting from subsequence [mid, mid + 1], we expand it to the left, storing all intervals we encounter until we exit the [lo, hi] window". How to implement this in linear time? Can someone explain this in more detail? It seems that I am missing something which may be obvious :)

Thanks!