题目描述

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.

输入格式

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 a single integer --- the maximum length of such a subsequence $b$.

5 2 6
1 3 4 2 5

3

2 1 1
1 1

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

Scoring

• ($1$ point): all $a_i$ are the same;
• ($3$ points): $a_i = a_{i+2}$ for all $1 \le i \le n-2$;
• ($9$ points): $n \le 20$;
• ($8$ points): $n \le 5000$;
• ($9$ points): $r - l \le 10$;
• ($10$ points): $l = 1, r \le 10^6$;
• ($13$ points): $r \le 10^6$;
• ($10$ points): $l = 1$;
• ($24$ points): $n \le 10^5$;
• ($13$ points): no additional constraints.