题目描述

给定一个包含 $n$ 个整数的序列 $a$，以及两个整数 $l$ 和 $r$。你需要找到序列 $a$ 的最长子序列 $b$，使得对于所有 $1 \le i < |b|$，满足 $l \le b_i + b_{i+1} \le r$。这里 $|b|$ 表示序列 $b$ 的元素个数。换句话说，你需要选择一个子序列，使得任意相邻两个数的和既不小于 $l$，也不大于 $r$。

一个数组的子序列是指通过从原序列中删除若干（可以是零个）元素得到的序列。

输入格式

第一行包含三个整数 $n$、$l$、$r$。

第二行包含 $n$ 个整数 $a_i$——序列的描述。

输出格式

输出一个整数——这样的子序列 $b$ 的最大长度。

输入样例 #1

5 2 6
1 3 4 2 5

输出样例 #1

3

输入样例 #2

2 1 1
1 1

输出样例 #2

1

说明提示

在第一个示例中，你可以选择子序列 $[1, 3, 2]$。$2 \leq 1 + 3 \leq 6$，$2 \leq 3 + 2 \leq 6$。

你也可以选择 $[1, 4, 2]$。

• （$1$ 分）：所有 $a_i$ 都相同；

• （$3$ 分）：对所有 $1 \le i \le n-2$，$a_i = a_{i+2}$；

• （$9$ 分）：$n \le 20$；

• （$8$ 分）：$n \le 5000$；

• （$9$ 分）：$r - l \le 10$；

• （$10$ 分）：$l = 1$，$r \le 10^6$；

• （$13$ 分）：$r \le 10^6$；

• （$10$ 分）：$l = 1$；

• （$24$ 分）：$n \le 10^5$；

• （$13$ 分）：无额外限制。

输入样例 #3

1 667969 882349
324536

输出样例 #3

1

数据范围

（$1 \le n \le 5 \cdot 10^5$，$1 \le l \le r \le 10^{17}$）

（$1 \le a_i \le r$）