\begin{tutorial}{Украшение}

\medskip
\textit{Автор задачи: Алексей Михненко}

\textit{Разработчик задачи: Виктор Романенко}
\medskip


\textbf{Формальная постановка задачи}

Дано $n$ отрезков на прямой. Разрешена следующая операция: выбрать два отрезка $(l_i, r_i)$ и $(l_j, r_j)$ и произвольным образом составить два новых отрезка из их четырёх границ.

Дано $q$ запросов $k_i$. Для каждого запроса требуется определить минимальное количество операций, необходимых для того, чтобы существовало подмножество из $k_i$ попарно пересекающихся отрезков.

\textbf{Основная идея}

Пусть все отрезки искомого множества пересекаются в некоторой точке $x$. Предположим, что:
\begin{itemize}
\item $c$ --- число отрезков, уже покрывающих точку $x$,
\item $l$ --- число отрезков, расположенных строго левее $x$,
\item $r$ --- число отрезков, расположенных строго правее $x$.
\end{itemize}

Заметим, что одной операцией можно взять один левый и один правый отрезок и перестроить их так, чтобы оба пересекали точку $x$. Следовательно, за одну операцию можно увеличить число отрезков, пересекающих $x$, на два.

Таким образом, максимальное количество отрезков, которые можно сделать пересекающимися в точке $x$, равно
\[
c + 2 \cdot \min(l, r).
\]

Для достижения этого значения потребуется $\min(l, r)$ операций. Если требуется получить промежуточное количество $k_i$, то достаточно выполнить
\[
\left\lceil \frac{k_i - c}{2} \right\rceil
\]
операций.

\textbf{Подгруппа 3. Отрезки не пересекаются}

В этом случае для любой точки выполняется $c \le 1$. Поэтому удобно рассматривать точку внутри центрального отрезка.

Для любой точки внутри такого отрезка выполняется $c = 1$, следовательно ответ для любого $k_i$ вычисляется по формуле
\[
\left\lceil \frac{k_i - 1}{2} \right\rceil.
\]

Если число отрезков чётное и $k_i = n$, то точка пересечения должна находиться между двумя центральными отрезками, где $c = 0$. Тогда ответ равен $n/2$. Поскольку $n$ чётно, это значение эквивалентно формуле выше.

\textbf{Подгруппа 4. $k_i = n$}

Если требуется сделать пересекающимися все отрезки, точка ответа должна находиться в позиции, где количество отрезков строго слева и строго справа одинаково.

Такую точку можно найти с помощью сканлайна. После нахождения соответствующих значений $c$, $l$ и $r$ ответ вычисляется по приведённой ранее формуле.
   
\textbf{Решение подгрупп 1, 2, 4, 5}

Выполним сканлайн. Для каждой открывающей границы отрезка и каждой закрывающей границы будем фиксировать значения:
\begin{itemize}
\item $c$ --- количество отрезков, покрывающих текущую точку,
\item $\min(l, r)$ --- минимальное число отрезков строго слева и строго справа.
\end{itemize}

При обработке закрывающей границы соответствующий отрезок уже не учитывается в $c$, однако считается лежащим строго слева, поскольку точка пересечения может находиться вне его границ.

Для каждой такой позиции можно вычислить минимальное число операций по формуле
\[
\left\lceil \frac{k_i - c}{2} \right\rceil,
\]
при условии, что
\[
k_i \le c + 2 \cdot \min(l, r).
\]

Минимум по всем таким позициям даёт ответ для подгрупп 1, 2, 4 и 5.

\textbf{Полное решение}

Остаётся оптимизировать вычисление ответов.

Для каждого $k$ от $1$ до $n$ заранее вычислим максимальное значение $c$, такое что возможно получить $k$ пересекающихся отрезков. Обозначим эту величину через $best[k]$.

Во время сканлайна для каждой позиции вычисляется значение
\[
c + 2 \cdot \min(l, r),
\]
которое показывает максимальное число отрезков, пересекающихся в данной точке после операций. Тогда выполняем обновление
\[
best[c + 2 \cdot \min(l, r)] = c.
\]

После завершения сканлайна пройдёмся по массиву $best$ справа налево и распространим максимум:
\[
best[i] = \max(best[i], best[i + 1]).
\]

Теперь $best[k]$ содержит максимальное число отрезков, уже покрывающих точку, из которой можно получить $k$ пересекающихся отрезков.

Ответ на запрос $k_i$ вычисляется по формуле
\[
\left\lceil \frac{k_i - best[k_i]}{2} \right\rceil.
\]

Итого $O(n \log n)$ на предпосчет из-за сортировки и $O(1)$ на запрос


\end{tutorial}
