На Антона тиснуть терміни — треба здавати всі роботи. Як часто це буває — продовжити дедлайн він не може...
Вам дана послідовність $$$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$$$.
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]$$$.