题目内容

某分拣控制系统沿传送方向设置 $n$ 个称重工位，编号 $1\sim n$。工位 $i$ 的重量为 $w_i$（单位：克）。系统按规则查询某一工位的上游偏低计数。查询期间各工位重量保持不变。

查询工位 $x$ 时，只统计其上游最近 $D$ 个工位，即编号落在区间 $[x-D,x-1]$ 内的工位。若 $x-D<1$，则左端取 $1$；若该区间为空，计数为 $0$。

在上述工位中，重量满足 $w_j\le w_x-K$ 的，计入偏低。$K=0$ 时，$w_j\le w_x$ 均计入。

共 $m$ 次查询，每次给出一个工位编号 $x$。

输入描述

第一行四个整数 $n$、$m$、$D$、$K$。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

接下来 $m$ 行，每行一个整数 $x$，表示查询工位 $x$。

约束

$1 \le n,m \le 10^5$

$0 \le D \le n$

$0 \le K \le 10^9$

$1 \le w_i \le 10^9$

$1 \le x \le n$

输出描述

对每次查询，输出一行一个整数：工位 $x$ 的上游偏低工位个数。

样例1

输入

5 4 2 1
10 8 9 5 7
3
5
4
1

输出

1
1
0
0

说明

$D=2$，$K=1$。重量为 $10,8,9,5,7$。

• 查询工位 $3$：上游为 $10$、$8$。$w_3-K=8$，仅 $8\le 8$，输出 $1$。
• 查询工位 $5$：上游为 $9$、$5$。$w_5-K=6$，仅 $5\le 6$，输出 $1$。
• 查询工位 $4$：上游为 $8$、$9$。$w_4-K=4$，二者均大于 $4$，输出 $0$。
• 查询工位 $1$：上游区间为空，输出 $0$。

样例2

输入

4 3 3 0
6 6 4 6
4
2
1

输出

3
1
0

说明

$D=3$，$K=0$，重量相等亦计入。重量为 $6,6,4,6$。

• 查询工位 $4$：上游为 $6$、$6$、$4$，均满足 $\le 6$，输出 $3$。
• 查询工位 $2$：上游仅 $6$，满足 $\le 6$，输出 $1$。
• 查询工位 $1$：上游区间为空，输出 $0$。