\begin{tutorial}{Марш овец}

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

\textit{Разработчик задачи: Юрий Федоров}
\medskip


\section{$T = 2$}

Заметим, что каждую секунду четность позиции каждой овцы меняется. Поэтому, если существует две овцы с разной четностью позиции, то ответ, очевидно \texttt{No}, так как всегда будет овца как на четной, так и нечетной позиции. В противном случае утверждается, что ответ всегда существует. Например, существует следующий алгоритм:

Если у текущего последнего столбца четность не совпадает с четностью позиций овец, то всегда можно обрезать участок на $1$ (так как на последнем столбце гарантированно не может быть овцы, ввиду четности). Таким образом можно достичь количества столбцов равному $1$, где все овцы гарантированно двигаются одинаково.

\section{$n \leq 3, m \leq 4$}

Если решить $T = 1$, то оставшихся случаев очень мало и их можно рассмотреть руками, либо же можно сделать перебор. В качестве состояния можно взять позиции каждой из овец, а также длину участка. И тогда есть два вида переходов: мы симмулируем одну секунду, либо же уменьшаем участок. Что можно реализовать при помощи любого графового алгоритма. Также существуют другие переборы.

\section{$n = 2$}

В случае $a_1 = 1, a_2 = m$ можно порисовать и понять, что ответ равен $\frac{m + 1}{2}$, и достаточно обрезать до этого размера через это же время.

\begin{center}
\includegraphics[]{explain-n2.1}
\end{center}

Теперь давайте посмотрим на два расстояния, отмеченных синим и красным цветом. Это расстояние от первой овцы до второй, и от второй до первой в порядке их пути. Тогда заметим, два факта:

\begin{enumerate}

\item Овцы будут двигаться одиннаково, тогда и только тогда, когда расстояние от одной до другой будет равно строго нулю.
\item После уменьшения размера поля на $1$, одно из этих расстояний уменьшается на $2$.

\end{enumerate}

Из чего сразу следует решение за $O(m)$: мы можем симмулировать их движение, и если обрезание уменьшает наименьшее из расстояний, то мы будет обрезать участок на $1$. И за $4 \cdot m$ операций этот процесс гарантированно будет завершен.

Теперь же научимся решать за $O(1)$: заметим, что если мы оставляем максимальное из расстояний, то если эта длина равна $x$, то ответ будет равен $\frac{x}{2} + 1$, так как если мы оставили длину $x$, то расстояние от одной овцы до другой будет равно $2 \cdot x - 2$. Тонкости же восстановления ответа, будут рассмотрены в полном решении.

\section{$T = 2$}

Немного разовьем идеи из $n = 2$. Заметим, что участок можно представить в виде цикла длины $2 \cdot m - 2$. А уменьшение длины участка на $1$ --- это уменьшение длины цикла на $2$:

\begin{center}
\includegraphics[scale=0.7]{explain-cycle.1}
\end{center}

На этой картинке приведен пример, где $3$ овцы находятся в позициях ($2, 4, 2$), их направления движения \texttt{RLL} (то есть синие точки --- это овцы). А для удобства дальнейшего повествования позиции перенесены в $0$ индексации. Красными вершинами помечены те, которые удаляются после уменьшения цикла.

Тогда расстояния до соседних овец можно представить в виде количества дуг от овцы до следующей по ней по циклу (здесь разными цветами обозначены различные дуги, которые представляют собой расстояния до соседних овец):

\begin{center}
\includegraphics[scale=0.7]{explain-cycle2.1}
\end{center}

Тогда заметим, что конструкция никак принципиально не отличается от ситуации $n = 2$. Нас также интересует только максимальное расстояние между соседними овцами на цикле. И можно, как и версии $n = 2, m \leq 2 \cdot 10^5$ просимулировать движения и обрезать в моменты, когда текущая длина не является максимумом, в этом случае получается асимптотика $O(n \cdot m)$. Либо же сказать, что ответ равен $\frac{x}{2} + 1$, где $x$ --- максимальное расстояние между соседними овцами.

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

Осталось только научиться восстанавливать. В случае $n, m \leq 1000$ мы уже научились решать, поэтому осталось  научиться восстанавливать при полных ограничениях.

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

\begin{itemize}

\item Перенумеруем массив таким образом, чтобы овца под номером $i$ оказалась самой последней овцой.
\item Давайте подождем время, чтобы последняя овца оказалась на позиции $m - 1$ на круге в $0$ индексации (или другими словами, чтобы она стояла в последнем столбце).
\item Тогда чтобы обрезать дугу от овцы $n - 1$ до овцы $n$, достаточно будет <<прокрутить>> цикл, чтобы овцы стала на позицию $m - 1 + \frac{d}{2}$, где $d$ --- длина дуги от овцы $n - 1$ до овцы $n$. А затем уменьшить длину участка на $\frac{d}{2}$, после чего овца под номером будет $n$ будет стоять на позиции $m - 1$ в цикле.
\item После этого мы можем игнорировать овцу под номером $n$ и обрабатывать овцу под номером $n - 1$ и так далее.

\end{itemize}

Ну и несложно заметить, что это действительно удалит все дуги, кроме максимальной.

\end{tutorial}
