Let's suppose first element of magic subarray is always smaller than the last. We can take care of the other case by reversing the array and running the same algorithm.

Therefore, to say [L,R] is magic, we have:

1. a[L] is the minimum element of a[L..R]
2. a[R] is the maximum element of a[L..R]

Let's maintain a segment tree that says for each index i <= R, what is the length of the biggest magic subarray that starts in i and ends in a position up to R.

Assuming the tree is in a correct state, when we increase R by 1, we only need to consider subarrays that end in new index R. Let's figure out which starting indices i are so that a[i..R] is magic:

Condition 1: For every index i, let Mi be the smallest index such that Mi > i and a[i] > a[Mi]. We have that condition 1 is satisfied for a[i..R] iff R < Mi. Note that whenever R passes Mi, i will never be a valid starting index anymore.

Condition 2: Let m be the largest index such that m < R and a[m] > a[R]. Clearly no subarray that starts before m and ends in R is magic, and also every subarray that starts after m satisfies condition 2, so for this condition R is only a valid ending point for m < i <= R.

For every i that satisfies both conditions, we should update tree[i] = R — i + 1. If we erase i from consideration when R = Mi, we can do this by lazy propagation in the interval m < i <= R. (If it is not obvious how to support the erasing operation, keep a value min_valid_start in the tree. Initially min_valid_start[i] = i for every i, and when i is erased, min_valid_start[i] = infinity.)

Having this tree, it should be simple to get answer to all queries after sorting them in order of increasing R.