\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)$ за запитване