# 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≤b_{i}+b_{i+1}≤r$ ($1≤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≤n≤5⋅10_{5}$, $1≤l≤r≤10_{17}$).

The second line contains $n$ integers $a_{i}$ ($1≤a_{i}≤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≤1+3≤6$. $2≤3+2≤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≤i≤n−2$;

($9$ points): $n≤20$;

($8$ points): $n≤5000$;

($9$ points): $r−l≤10$;

($10$ points): $l=1,r≤10_{6}$;

($13$ points): $r≤10_{6}$;

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

($24$ points): $n≤10_{5}$;

($13$ points): no additional constraints.