B. MiniMax
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers, which may be negative, zero or positive, and a positive integer $$$k$$$.

You must answer $$$q$$$ queries. Each query gives two positions $$$l$$$ and $$$r$$$. Your task is to split the subarray $$$a[l..r]$$$ into the minimum possible number of non-empty contiguous segments, such that, in each segment, the difference between its maximum element and its minimum element is less than or equal to $$$k$$$.

The segments must cover exactly the queried subarray, without overlapping and keeping the original order of the elements. A segment with a single element has difference zero.

Positions are numbered starting from $$$1$$$. The array and the value of $$$k$$$ are the same for all queries. The queries are independent and do not modify the array.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^{5}$$$): the length of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leq a_i \leq 10^{9}$$$).

The third line contains an integer $$$k$$$ ($$$1 \leq k \leq 10^{9}$$$).

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), representing a query on $$$a[l..r]$$$.

The input contains a single test case and is read from standard input.

Output

For each query, print on a line of standard output the minimum number of segments required, in the same order in which the queries are received.

Examples
Input
7 3
1 5 3 2 7 6 4
3
1 7
2 5
3 4
Output
3
2
1
Input
6 4
-3 -1 0 2 2 -2
3
1 6
2 5
3 3
5 6
Output
3
1
1
2
Note

Explanation for example 1

For $$$[1, 7]$$$, an optimal partition is $$$[1] \mid [5, 3, 2] \mid [7, 6, 4]$$$. The differences are $$$0$$$, $$$3$$$ and $$$3$$$. It is mandatory to cut between $$$1$$$ and $$$5$$$, and between $$$2$$$ and $$$7$$$, because each of those consecutive pairs has a difference greater than $$$3$$$. Therefore, at least three segments are needed.

For $$$[2, 5]$$$, an optimal partition is $$$[5, 3, 2] \mid [7]$$$. The whole subarray has difference $$$7 - 2 = 5 \gt 3$$$, so a single segment is not enough.

For $$$[3, 4]$$$, the segment $$$[3, 2]$$$ has difference $$$1$$$, so the answer is $$$1$$$.

Explanation for example 2

For $$$[1, 6]$$$, an optimal partition is $$$[-3, -1, 0] \mid [2, 2] \mid [-2]$$$. There must be a cut before the first $$$2$$$, because it cannot share a segment with $$$-3$$$, and another cut between the last $$$2$$$ and $$$-2$$$, whose difference is $$$4$$$. Those cuts are different, so at least three segments are needed.

For $$$[2, 5]$$$, the subarray $$$[-1, 0, 2, 2]$$$ has difference $$$3$$$ and fits in a single segment.

For $$$[3, 3]$$$, the subarray contains only the zero and requires one segment.

For $$$[5, 6]$$$, the values $$$2$$$ and $$$-2$$$ have difference $$$4$$$ and must be placed in separate segments.