Это простая версия задачи. Единственные отличия между двумя версиями заключаются в ограничениях на \(m\) и \(q\). В этой версии \(m, q \le 10^5\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Нарек и Цовак были заняты подготовкой этого раунда, поэтому они не успели сделать домашнее задание, и они решили украсть домашнее задание Давида. Их строгая учительница заметила, что у Давида нет домашнего задания, и теперь хочет его наказать. Она наняла других учительниц, чтобы помочь поймать Давида, и теперь \(m\) учительниц вместе преследуют его. К счастью, они находятся в большом классе, поэтому у Давида есть много мест, где можно спрятаться.
Класс можно представить как последовательность клеток, пронумерованных от \(1\) до \(n\), расположенных на прямой.
Изначально все \(m\) учительниц и Давид находятся в различных клетках. Затем они делают ходы. Во время каждого хода:
- Давид перемещается в соседнюю клетку или остается в текущей.
- Затем каждая из \(m\) учительниц одновременно перемещается в соседнюю клетку или остается в текущей.
Процесс продолжается, пока Давид не будет пойман. Давид пойман, если любая из учительниц (возможно, более одной) находится в той же клетке, что и Давид. Все участники видят ходы других, поэтому все действуют оптимально.
Ваша задача — посчитать, сколько ходов потребуется учительницам, чтобы поймать Давида, если они все действуют оптимально.
Оптимальность действий означает, что ученик делает свои ходы так, чтобы максимизировать количество ходов, необходимых учительницам, чтобы поймать его. А учительницы координируются друг с другом, чтобы сделать свои ходы так, чтобы минимизировать количество ходов, необходимых для поимки ученика.
Кроме того, поскольку Нарек и Цовак считают эту задачу простой, они решили задать вам \(q\) запросов о положении Давида.
Примечание
В единственном запросе первого примера ученик может убежать в клетку \(1\). Учительнице потребуется пять ходов, чтобы добраться из клетки \(6\) до клетки \(1\), поэтому ответ — \(5\).
Во втором запросе второго примера ученик может просто остаться в клетке \(3\). Учительница, изначально находящаяся в клетке \(4\), может добраться до клетки \(3\) за один ход. Следовательно, ответ — \(1\).