Послідовність

На Антона тиснуть терміни — треба здавати всі роботи. Як часто це буває — продовжити дедлайн він не може...

Вам дана послідовність $a$ з $n$ цілих чисел, і два цілі числа $l$ та $r$. Вам треба знайти найдовшу таку підпослідовність $b$ послідовності $a$, що $l\le b_i+b_{i+1}\le r$ ($1\le i<|b|$). Тут $|b|$ позначає кількість елементів послідовності $b$. Іншими словами, вам потрібно вибрати таку підпослідовність, що сума кожних двох сусідніх чисел не менша за $l$ та не більша за $r$.

Підпослідовність масиву — це послідовність, яку можна отримати видаленням кількох (можливо жодного) елементів початкової послідовності.

Вхідні дані

Перший рядок містить три цілі числа $n$, $l$, $r$ ($1\le n\le 5\cdot 10^5$, $1\le l\le r\le 10^{17}$).

Другий рядок містить $n$ цілих чисел $a_i$ ($1\le a_i\le r$) — опис послідовності.

Вихідні дані

Виведіть єдине ціле число — максимальну довжину такої підпослідовності $b$.

Приклади

Примітка

У першому прикладі можна вибрати таку підпослідовність $[1,3,2]$. $2\le 1+3\le 6$. $2\le 3+2\le 6$.

Також можна вибрати й $[1,4,2]$.

Оцінювання

1. ($1$ бал): всі $a_i$ однакові;

2. ($3$ бали): $a_i=a_{i+2}$ для всіх $1\le i\le n-2$;

3. ($9$ балів): $n\le 20$;

4. ($8$ балів): $n\le 5000$;

5. ($9$ балів): $r-l\le 10$;

6. ($10$ балів): $l=1,r\le 10^6$;

7. ($13$ балів): $r\le 10^6$;

8. ($10$ балів): $l=1$;

9. ($24$ бали): $n\le 10^5$;

10. ($13$ балів): без додаткових обмежень.