407767: GYM102891 D Towers

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.

• Subtask 1 (18 points): $$$n, q \le 1000$$$
• Subtask 2 (31 points): $$$n, q \le 10^5$$$
• Subtask 3 (51 points): No additional constraints

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