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.
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.
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.
7 31 5 3 2 7 6 431 72 53 4
3 2 1
6 4-3 -1 0 2 2 -231 62 53 35 6
3 1 1 2
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.
