\begin{tutorial}{Infection Investigation}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Фёдор Ушаков\\
         Разработка: & Леонид Данилевич\\
     \end{tabular}
}

Будем отвечать на запросы оффлайн, применив принцип <<разделяй и властвуй>>. А именно, напишем рекурсивную функцию, принимающую $1 \le \mathrm{lf} \le \mathrm{rg} \le n$, и получающую ответы для запросов $(l, r)$ при условии $\mathrm{lf} \le l \le r \le \mathrm{rg}$. Пусть $\mathrm{m} = \lfloor\frac{\mathrm{lf}+\mathrm{rg}}{2}\rfloor$, тогда функция отвечает на запросы $(l, r)$, не содержащие $m$, рекурсивно. Осталось разобраться с запросами $(l, r)$, такими, что $\mathrm{lf} \le l \le m \le r \le \mathrm{rg}$.

Для этого насчитаем стандартными методами (при помощи двоичного поиска или дерева отрезков / дерева Фенвика) длины наибольшей возрастающей подпоследовательности на префиксах $[a_m, \ldots, a_{\mathrm{rg}}]$ и суффиксах $[a_{\mathrm{lf}}, \ldots, a_{m-1}]$. Пусть отрезок $(a_l, \ldots, a_r)$ бьётся на два, и длины возрастающей подпоследовательности в этих частях равны $x, y \ge 1$. Ясно, что в таком случае ответ на этот запрос заключён в отрезке $[\max(x, y), x + y]$. Если $x = y = 1$, то необходимо проверить, является ли подмассив $a_l, \ldots, a_r$ строго убывающим, а во всех остальных случаях $\lfloor\frac{\max(x, y) + (x + y)}{2}\rfloor$ является достаточно хорошим приближением. 

В самом деле, с одной стороны $\lfloor\frac{\max(x, y) + (x + y)}{2}\rfloor \le \frac{\max(x, y) + (x + y)}{2} \le \frac{3}{2}\max(x, y)$, а с другой стороны при $\max(x, y) \ge 3$: $\lfloor\frac{\max(x, y) + (x + y)}{2}\rfloor \ge \frac{\max(x, y) + (x + y) - 1}{2} \ge \frac{2}{3}(x+y)$; перебор случаев показывает, что при $\max(x, y) = 2$ тоже $\lfloor\frac{\max(x, y) + (x + y)}{2}\rfloor \ge \frac{2}{3}(x+y)$.

Итого асимптотика высчитывается по формуле $T(n) = 2T(n/2) + \mathcal{O}(n\log n)$, откуда алгоритм работает за $\mathcal{O}(n\log^2 n)$.

\end{tutorial}
