На Антона тиснуть терміни — треба здавати всі роботи. Як часто це буває — продовжити дедлайн він не може...
Вам дана послідовність з цілих чисел, і два цілі числа та . Вам треба знайти найдовшу таку підпослідовність послідовності , що l \le b_i + b_{i+1} \le r (1 \le i < |b|). Тут позначає кількість елементів послідовності . Іншими словами, вам потрібно вибрати таку підпослідовність, що сума кожних двох сусідніх чисел не менша за та не більша за .
Підпослідовність масиву — це послідовність, яку можна отримати видаленням кількох (можливо жодного) елементів початкової послідовності.
Перший рядок містить три цілі числа , , (1 \le n \le 5 \cdot 10^5, 1 \le l \le r \le 10^{17}).
Другий рядок містить цілих чисел a_i (1 \le a_i \le r) — опис послідовності.
Виведіть єдине ціле число — максимальну довжину такої підпослідовності .
Приклад
Приклад 1
У першому прикладі можна вибрати таку підпослідовність [1, 3, 2]. 2 \leq 1 + 3 \leq 6. 2 \leq 3 + 2 \leq 6.
Також можна вибрати й [1, 4, 2].
( бал): всі a_i однакові;
( бали): a_i = a_{i+2} для всіх 1 \le i \le n-2;
( балів): n \le 20;
( балів): n \le 5000;
( балів): r - l \le 10;
( балів): l = 1, r \le 10^6;
( балів): r \le 10^6;
( балів): l = 1;
( бали): n \le 10^5;
( балів): без додаткових обмежень.