Sequence
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

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.

Examples

Input
5 2 6
1 3 4 2 5
Output
3
Input
2 1 1
1 1
Output
1

Note

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]$$$.