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.

Input

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

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

Examples

Note

In the first example, you can select the subsequence $[1,3,2]$. $2\le 1+3\le 6$. $2\le 3+2\le 6$.

You can also select $[1,4,2]$.

Scoring

1. ($1$ point): all $a_i$ are the same;

2. ($3$ points): $a_i=a_{i+2}$ for all $1\le i\le n-2$;

3. ($9$ points): $n\le 20$;

4. ($8$ points): $n\le 5000$;

5. ($9$ points): $r-l\le 10$;

6. ($10$ points): $l=1,r\le 10^6$;

7. ($13$ points): $r\le 10^6$;

8. ($10$ points): $l=1$;

9. ($24$ points): $n\le 10^5$;

10. ($13$ points): no additional constraints.