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 <= l <= r <= 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 <= b <= e <= n$), find the number of pairs $(l, r)$ such that $b <= l <= r <= 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 <= n, k <= 10^6$).
The second line contains $n$ integers $h_1, h_2, \\dots, h_n$ ($1 <= h_i <= 10^6$).
The third line contains an integers $q$ ($1 <= q <= 10^6$).
Then $q$ lines follow. Each line contains two integers $b, e$ ($1 <= b <= e <= n$) describing a query.
For each query, output the answer on one line.
## Input
The first line contains two integers $n, k$ ($1 <= n, k <= 10^6$).The second line contains $n$ integers $h_1, h_2, \\dots, h_n$ ($1 <= h_i <= 10^6$).The third line contains an integers $q$ ($1 <= q <= 10^6$).Then $q$ lines follow. Each line contains two integers $b, e$ ($1 <= b <= e <= n$) describing a query.
## Output
For each query, output the answer on one line.
[samples]
## Scoring
Subtask 1 (18 points): $n, q <= 1000$ Subtask 2 (31 points): $n, q <= 10^5$ Subtask 3 (51 points): No additional constraints
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $.
Let $ K = \{(s_i, w_i) \mid i \in \{1, \dots, n\}\} $ be the set of kk’s cards, where $ s_i \in \Sigma^* $ (string of lowercase letters, $ 1 \le |s_i| \le 5 $) and $ w_i \in \mathbb{R} $ (float, $ 0 \le w_i \le 100 $, one decimal digit).
Let $ B = \{(t_j, v_j) \mid j \in \{1, \dots, q\}\} $ be the set of bm’s cards, with same constraints on $ t_j, v_j $.
**Dominance Relation**
For two cards $ (s, w) $ and $ (t, v) $, we say $ (s, w) $ *dominates* $ (t, v) $ if:
1. $ s <_{\text{lex}} t $, **or**
2. $ s = t $ and $ w > v $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le q \le 10^5 $
3. $ 1 \le |s_i|, |t_j| \le 5 $, all characters lowercase
4. $ 0 \le w_i, v_j \le 100 $, with exactly one decimal digit
**Objective**
For each card $ (t_j, v_j) \in B $, compute:
$$
f(j) = \left| \left\{ (s_i, w_i) \in K \mid (s_i, w_i) \text{ dominates } (t_j, v_j) \right\} \right|
$$
Output $ f(j) $ for each $ j \in \{1, \dots, q\} $.