题目描述

Anton 感到压力山大——他必须提交所有作业。但正如常有的情况——他无法延长期限……

给定一个包含 $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$（$1 \le n \le 5 \cdot 10^5$，$1 \le l \le r \le 10^{17}$）。
• 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le r$）——序列的描述。

输出格式

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

5 2 6
1 3 4 2 5

3

2 1 1
1 1

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$ 分）：无额外限制。

翻译由 DeepSeek V3 完成