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

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

1,5 секунди
512 мегабайтів
Середня

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

Вам дана послідовність з цілих чисел, і два цілі числа та . Вам треба знайти найдовшу таку підпослідовність послідовності , що 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) — опис послідовності.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

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

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

Оцінювання

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

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

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

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

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

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

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

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

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

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