The task is to find the longest magical subarray of a subarray from the original array. An array is magical if all the values of all elements are between the values of the first and last element of that array. The solution for ~70\%~ of total points has a complexity of ~\mathcal O(N \sqrt N)~ and will not be explained here. Regarding the solution for all points, special thanks to Mislav Bradač for coming up with such a solution and implementing it.

To begin with, we will solve the case when the first element is the minimal element in the magical subarray, and the last element is the maximal. The case when the first element is maximal and the last minimal is solved analogously over an array with all elements replaced with their negative values.

Let's sort all queries with regards to the right end and now sweep from left to right, adding the elements and processing the queries. The idea is to, while sweeping and located at position ~p~, maintain the array ~A[x]~, such that ~A[x] =~ longest subarray whose left end is at position ~x~, and the right end wherever between ~(x, p]~. If we have such an array, it is easy to see that, at position ~p~, the answer for query ~[L, p]~ is the maximal value ~A[x]~, for ~x~ from the interval ~[L, p]~. Let's try to efficiently maintain this array. The structure that arises as a solution to this kind of problem is usually the tournament structure. It is necessary to update some positions when we add a new value ~x~ at position ~p~. Firstly, given the fact that we are solving the first case when the last element is maximal, and the first minimal, it is obvious that the value ~x~ will only be important until the first left position where the value ~v > x~ is located. We will label this position as ~l~. The details of finding such a position are left for later. Additionally, all larger values to the left of ~x~ need to be labeled as unusable because they could never be the left end of the interval that passes over ~x~ because ~x~ is smaller than them. We will describe the details of finding such positions later, also. For the remaining positions from the interval ~[L, x]~, we will label the potentially rightmost end as ~x~.

Let's now look at all the operations our tournament structure must support:

1. It needs to be able to exclude a position ~x~ as the left end. In other words, that it will not be possible in the future for it to be the left position for a value to the right.
2. It needs to be able to set the rightmost position that can be the end of some interval to a new value ~x~.
3. It needs to be able to determine the current maximal value in an interval.

Therefore, the entire idea of the tournament is to store for each position ~x~, until the current position ~p~, what the rightmost position ~y~ was while ~x~ was still alive, or the distance between ~y~ and ~x~. All these operations are possible to achieve using propagation. The tournament will store the leftmost alive element from the interval in a node, the current rightmost position for that interval and the largest distance between the left and right position of the magical subarray. The propagation operations of these values are not difficult to derive, and we leave that as an exercise to the reader. What we still haven't covered is finding the first larger value and removing all larger values as unusable for the left end from the tournament. We do this by maintaining two stacks while moving in the sweep, one to search for the first smaller number to the left, the other to search for the first larger number to the left. All numbers that are removed while searching the first smaller number to the left will be exactly the ones we need to kill in the tournament are not anymore possible left ends. The total complexity of the solution is ~\mathcal O((Q+N) \log N)~.