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.
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 a single integer — the maximum length of such a subsequence .
Example
Example 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].
( point): all a_i are the same;
( points): a_i = a_{i+2} for all 1 \le i \le n-2;
( points): n \le 20;
( points): n \le 5000;
( points): r - l \le 10;
( points): l = 1, r \le 10^6;
( points): r \le 10^6;
( points): l = 1;
( points): n \le 10^5;
( points): no additional constraints.