P15070 [UOI 2024 II Stage] Sequence

Anton is under pressure --- he has to submit all the assignments. As often happens --- he cannot extend the deadline... You are given a sequence $a$ of $n$ integers, and two integers $l$ and $r$. You need to find the longest subsequence $b$ of the sequence $a$ such that $l \le b_i + b_{i+1} \le r$ ($1 \le i < |b|$). Here, $|b|$ denotes the number of elements in the sequence $b$. In other words, you need to select a subsequence such that the sum of any two adjacent numbers is not less than $l$ and not greater than $r$. A subsequence of an array is a sequence that can be obtained by deleting several (possibly none) elements from the original sequence.

The first line contains three integers $n$, $l$, $r$ ($1 \le n \le 5 \cdot 10^5$, $1 \le l \le r \le 10^{17}$). The second line contains $n$ integers $a_i$ ($1 \le a_i \le r$) --- the description of the sequence.

Output a single integer --- the maximum length of such a subsequence $b$.

In the first example, you can select the subsequence $[1, 3, 2]$. $2 \leq 1 + 3 \leq 6$. $2 \leq 3 + 2 \leq 6$. You can also select $[1, 4, 2]$. ### Scoring - ($1$ point): all $a_i$ are the same; - ($3$ points): $a_i = a_{i+2}$ for all $1 \le i \le n-2$; - ($9$ points): $n \le 20$; - ($8$ points): $n \le 5000$; - ($9$ points): $r - l \le 10$; - ($10$ points): $l = 1, r \le 10^6$; - ($13$ points): $r \le 10^6$; - ($10$ points): $l = 1$; - ($24$ points): $n \le 10^5$; - ($13$ points): no additional constraints.