Editorial

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

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

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