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

Будемо йти зліва направо по масиву і тримати значення $$$dp_a$$$ — максимальна довжина підпослідовності, що закінчується в елементі зі значенням $$$a$$$. Тоді можна перераховувати $$$dp_{a_i} = \max(dp_{a_i}, dp_j + 1$$$), так що $$$l \le j + a_i \le r$$$.

Що робити тепер? Перераховуймо $$$dp$$$ за допомогою дерева відрізків. Будемо запитувати максимум на відрізку $$$[l-a_i;r-a_i]$$$, і оновлювати в точці $$$a_i$$$. Це можна робити за допомогою неявного дерева відрізків, або компресії координат.

Загальна асимптотика — $$$\mathcal{O}(N \log N)$$$ з компресією.