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