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$$$.
5 2 6 1 3 4 2 5
3
2 1 1 1 1
1
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]$$$.