G. Delete or not
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a strictly increasing sequence of $$$n$$$ positive integers $$$A = [a_1, a_2, \ldots, a_n]$$$.

You need to answer $$$q$$$ independent queries. In each query, you are given an interval $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$). Let $$$B$$$ be the contiguous subsegment $$$[a_l, a_{l+1}, \ldots, a_r]$$$.

You can perform the following operation on the sequence $$$B$$$ any number of times (possibly zero):

  • Choose an index $$$i$$$ ($$$2 \le i \le \lvert B \rvert - 1$$$) such that $$$2B_i \le B_{i-1} + B_{i+1}$$$.
  • Remove $$$B_i$$$ from the sequence $$$B$$$. After the removal, the remaining elements are concatenated without changing their relative order, and the length of $$$B$$$ decreases by $$$1$$$ (i.e., the original $$$B_{i-1}$$$ and $$$B_{i+1}$$$ become adjacent).

For each query, find the minimum possible length of the sequence $$$B$$$ after performing any number of valid operations.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the length of the sequence and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \lt a_2 \lt \ldots \lt a_n \le 10^9$$$) — the elements of the sequence.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the boundaries of the query.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$3 \cdot 10^5$$$.

Output

For each query, output a single integer on a new line — the minimum possible length of the sequence $$$B$$$ after any number of valid operations.

Example
Input
2
5 4
1 5 6 8 9
1 5
1 3
2 5
4 5
6 5
2 3 7 8 10 15
1 6
2 5
1 4
3 6
5 5
Output
4
3
3
2
2
3
3
2
1