P15070 [UOI 2024 II Stage] Sequence

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$ 的最大长度。

在第一个示例中，你可以选择子序列 $[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 完成