Послідовність
ліміт часу на тест
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]$$$.