Послідовність
ліміт часу на тест
1.5 seconds
ліміт використання пам'яті на тест
512 megabytes
введення
standard input
виведення
standard output

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

Вам дана послідовність $$$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. ($$$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$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    5 2 6
    1 3 4 2 5

Вихідні дані

    3

Вхідні дані

    2 1 1
    1 1

Вихідні дані

    1

Пояснення

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

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