It is well known that monks are good at transporting food between places, especially hot liquids.
There are $$$n$$$ towers in a row. The $$$i$$$-th tower is $$$h_i$$$ meters tall. For two integers $$$l, r$$$ where $$$1 \le l \le r \le n$$$, a soup-carrying mission on $$$[l, r]$$$ is a mission in which a monk has to carry a bowl of hot soup from the $$$l$$$-th tower to the $$$r$$$-th tower. If the difference between the maximum and minimum heights among the towers $$$l, l+1, \dots, r$$$ exceeds $$$k$$$, then the monk will spill their soup onto the floor during the mission, failing it horribly. Otherwise, the mission is successful.
Given integers $$$b$$$ and $$$e$$$ ($$$1 \le b \le e \le n$$$), find the number of pairs $$$(l, r)$$$ such that $$$b \le l \le r \le e$$$ and that you can assign a successful soup-carrying mission on $$$[l, r]$$$ to a monk. You have to answer $$$q$$$ queries.
The first line contains two integers $$$n, k$$$ ($$$1 \le n, k \le 10^6$$$).
The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 10^6$$$).
The third line contains an integers $$$q$$$ ($$$1 \le q \le 10^6$$$).
Then $$$q$$$ lines follow. Each line contains two integers $$$b, e$$$ ($$$1 \le b \le e \le n$$$) describing a query.
For each query, output the answer on one line.
10 2 8 6 1 2 7 6 9 2 8 4 10 4 9 3 5 2 9 3 7 3 8 8 8 1 10 3 4 2 10 1 3
7 4 10 7 8 1 13 3 11 4
