时空限制

1S/512M

题目描述

给定一个长度为 $m$ 的序列 $b$，我们称 $b$ 是“好序列”，当且仅当序列的极差不超过一个常数 $k$，即：

其中，符号 $\max_{i=1}^m b_i$ 表示序列 $b$ 中 $m$ 个元素的最大值，$\min_{i=1}^m b_i$ 表示序列 $b$ 中 $m$ 个元素的最小值。

现在给定一个长度为 $n$ 的序列 $a$ 和 $q$ 组询问，每组询问给定两个整数 $l, r$，你需要判断 $a_l, a_{l+1}, \cdots, a_r$ 是否是“好序列”。

格式

输入格式

第一行包含三个整数 $n, q, k$，$n$ 和 $q$ 表示序列的长度和询问的个数，$k$ 的含义详见题目描述。

第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$。

接下来的 $q$ 行，每行包含两个整数 $l, r$，表示询问区间的左右端点。

输出格式

对于每组询问输出一行，如果 $a_l, a_{l+1}, \cdots, a_r$ 是“好序列”那么输出 Yes，否则输出 No。

样例

样例输入 #1

6 5 3
1 1 4 5 1 4
1 3
1 4
2 4
5 6
4 6

样例输出 #1

Yes
No
No
Yes
No

样例解释 #1

对于第 $1$ 个询问，区间 $[1, 3]$ 的数为 $\{1, 1, 4\}$，最大值 $4$，最小值 $1$，差为 $3$，满足 $\le 3$，输出 Yes。

对于第 $2$ 个询问，区间 $[1, 4]$ 的数为 $\{1, 1, 4, 5\}$，最大值 $5$，最小值 $1$，差为 $4$，不满足 $\le 3$，输出 No。

数据规模

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10^3$，$0 \le k, a_i \le 10^9$，$1 \le l \le r \le n$。