← 返回题目列表

Codeforces · 550/B

B. 准备奥林匹克竞赛

中文机器翻译题面 查看原题

你有n个问题。您已将第 i 个难度估计为整数 ci。现在您想要使用您所做的一些问题来准备竞赛的问题集。

竞赛的问题集必须至少包含两个问题。你认为比赛题目的总难度必须至少为l,最多为r。另外,您认为所选问题中最简单和最难的难度之间的差异必须至少为 x。

找出为比赛选择问题集的方法数量。

输入

第一行包含四个整数 n、l、r、x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) - 分别是您拥有的问题数量、问题集总难度的最小值和最大值以及包中最难问题和最简单问题之间的最小难度差异。

第二行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ 106) — 每个问题的难度。

输出

打印为比赛选择合适问题集的方法数量。

示例

输入 #1

3 5 6 1
1 2 3

输出 #1

2

输入 #2

4 40 50 10
10 20 30 25

输出 #2

2

输入 #3

5 25 35 10
10 10 20 10 20

输出 #3

6

注意

在第一个示例中,有两组是合适的,一组由第二个问题和第三个问题组成,另一组由所有三个问题组成。

在第二个示例中,有两组问题是合适的 - 难度为 10 和 30 的问题组以及难度为 20 和 30 的问题组。

在第三示例中,由一个难度为10的问题和一个难度为20的问题组成的任何集合都是合适的。