\begin{tutorial}{Послідовність}

Будемо йти зліва направо по масиву і тримати значення $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)$ з компресією.

\end{tutorial}
