Sasha is tired of the heavy city life and decided to move to the countryside. To occupy his time, he decided to raise sheep. For this purpose, he acquired a rectangular field in the village, which can be represented as a grid of size $n \times m$, where the rows are numbered from top to bottom with numbers from $1$ to $n$, and the columns are numbered from left to right with numbers from $1$ to $m$.

On his field, Sasha bought $n$ sheep, each of which he assigned a whole row. Initially, the $i$-th sheep was placed in the cell with coordinates $(i, a_i)$ (in row number $i$ and column number $a_i$). Sasha found out that the sheep move only horizontally according to the following rules:

\begin{itemize}

\item If there is exactly one column in the field, the sheep do not move.

\item Initially, the $i$-th sheep is in cell $(i, a_i)$, and each sheep has an initial direction in which it moves --- either left or right. There is no sheep that is in the first column and moves left, nor is there any sheep that is in the last column and moves right.

\item Every second, each sheep moves one column to the left if it is moving left; otherwise, it moves one column to the right.

\item If after moving a sheep ends up in column $1$ and is moving left, or if a sheep ends up in the last column and is moving right, it changes its direction to the opposite. Thus, the sheep never leave the boundaries of the field.

\end{itemize}

\begin{center}
  \includegraphics[scale=0.75]{sheep-move.1}

\vspace{0.5cm}
\begin{minipage}{14cm}
{\footnotesize Here is an example of the sheep's movement, where initially the first sheep was in column $1$ and moved to the right, and the second was in column $3$ and moved to the left. The first picture shows the state at the beginning, the second after one second, the third after $2$ seconds from the start of movement, and the fourth after $3$ seconds from the start of movement.}
\vspace{0.5cm}
\end{minipage}
\end{center}

Sasha does not like that the sheep move so chaotically; he wants all the sheep to move uniformly. This means that all sheep should be in the same column and have the same direction of movement. To achieve this, Sasha can trim his field several (possibly zero) times as follows:

\begin{itemize}

\item He chooses a time $t$ (how many seconds have passed since the initial start of the sheep's movement) and the number of columns $x$ that will remain in the field after trimming.

\item All sheep at time $t$ must strictly lie within the field of size $n \times x$. This means that for any $i$ from $1$ to $n$, the $i$-th sheep at time $t$ must be in cell $(i, y_i)$, where $1 \leq y_i \leq x$. Otherwise, such a trimming of the field is not allowed.

\item After this operation, starting from time $t$, the number of columns on the field decreases to $x$.

\item Each sheep that is in the last column and moves to the right changes its direction to the opposite.

\end{itemize}

Detailed examples of the trimming process are described in the notes section.

Sasha wants to know if it is possible to achieve that all sheep move uniformly by trimming the field several times. If this is possible, Sasha wants to know what the maximum number of columns that can remain on the field is and how exactly he can achieve this. Help Sasha solve this problem!