Sequence#270

Sequence

1.5 seconds
512 megabytes
Medium

Anton is under pressure — he has to submit all the assignments. As often happens — he cannot extend the deadline...

You are given a sequence of integers, and two integers and . You need to find the longest subsequence of the sequence such that l \le b_i + b_{i+1} \le r (1 \le i < |b|). Here, denotes the number of elements in the sequence . In other words, you need to select a subsequence such that the sum of any two adjacent numbers is not less than and not greater than .

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 , , (1 \le n \le 5 \cdot 10^5, 1 \le l \le r \le 10^{17}).

The second line contains 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 .

Examples

Example

Loading
Loading

Example 1

Loading
Loading

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

Scoring

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

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

  3. ( points): n \le 20;

  4. ( points): n \le 5000;

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

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

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

  8. ( points): l = 1;

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

  10. ( points): no additional constraints.