I saw a problem somewhere and I want to know the most efficient for this problem.

You're given t testcases an array aof n elements and q queries. Each query gives you a range l and r. You want to get a subsegment in [l,r] so that the subsegment is sorted in increasing order.

For example

Input

3 5 2 1 2 3 5 4 1 5 3 5 5 2 1 2 3 4 5 1 5 3 5 6 5 1 4 2 3 9 1 1 3 1 2 1 6 3 6 6 6

Output

4 2 5 3 2 2 3 3 1

I heard that problem can bo solved with segment trees but I don't know how