Starting from a vertex with color \(A_i\) and a piece placed on it, we create a tree with colored vertices by performing the following steps for \(i=2,3,\dots,N\) in this order:

• Let \(pos\) be the current position of the piece. If the color of the vertex at \(pos\) is \(A_i\), do nothing. If there is an adjacent vertex to \(pos\) with color \(A_i\), move the piece there. If no such vertex exists, create a new adjacent vertex to \(pos\) with color \(A_i\) and move the piece there. Note that due to the way vertices are created, the colors of adjacent vertices are always distinct.

This way, the state of the sequence corresponds to a walk on this tree (where staying in place is also allowed), and the operation changes a walk \(u\rightarrow v\rightarrow v\rightarrow \dots \rightarrow v\rightarrow u\) to a walk \(u\rightarrow u\rightarrow u\rightarrow \dots \rightarrow u\rightarrow u\).

Let \(start\) and \(goal\) be the starting and ending points of the walk. These do not change due to the operations. If the walk, ignoring the parts where it stays in place, is not a simple path connecting \(start\) and \(goal\), there will always be such \(u\) and \(v\) with the aforementioned walk. Therefore, the problem can be considered as finding the minimum cost to change the walk into a simple path connecting \(start\) and \(goal\).

We consider the minimum cost when a series of operations changes the walk \((v_1,v_2,\dots,v_n)\) to \((v'_1,v'_2,\dots,v'_n)\). If \(v_i\) is changed by an operation, it is changed to an adjacent vertex, so the total distance on the tree between \(v_i\) and \(v'_i\) is at most the cost of the changes. Thus, a lower bound of the total cost of changes is the sum of the distances between \(v_i\) and \(v'_i\), and this lower bound can be achieved by performing operations on the parts visiting the leaves of a subtree, focusing only on the parts the walk passes through.

Based on the above, we calculate the minimum cost. First, consider the parts of the initial walk that are off the path connecting \(start\) and \(goal\), \(\dots \rightarrow a \rightarrow b \rightarrow \dots \rightarrow b \rightarrow a \rightarrow \dots\) (where \(a\) is a vertex on the path connecting \(start\) and \(goal\), and \(b\) is not on the path). In any series of operations, at some point, the part \(b \rightarrow \dots \rightarrow b\) will be converted to a walk that stays at \(a\). Therefore, this part can be pre-converted to stay at \(a\), and the minimum cost of this conversion can be easily obtained as the sum of the distances to \(a\). This way, the initial walk can be considered as moving back and forth on the path connecting \(start\) and \(goal\), and the following problem needs to be solved:

We have an integer sequence \(V=(v_1,v_2,\dots,v_n)\) such that:

• \(v_1=1, v_n=\max_{1\leq i \leq n} v_i\)
• \(|v_i-v_{i+1}| \in \{0,1\}\)

Find the minimum value of \(\sum |v_i-v'_i|\) for an integer sequence \(V'=(v'_1,v'_2,\dots,v'_n)\) that satisfies the following conditions:

• \(v'_1=v_1, v'_n=v_n\)
• \(v'_i \leq v'_{i+1}\)
• If \(v'_i \neq v'_{i+1}\), then \(v_i=v'_i\) and \(v_{i+1}=v'_{i+1}\).

This can be solved using dynamic programming in \(O(N)\) time with \(dp[k]=\) (the minimum value of \(\sum_{k \leq i} |v_i-v'_i|\) when \(v'_k=v_k\)), as follows:

• When \(v_{k+1}=v_k+1\), update \(dp[k] \leftarrow \min(dp[k],dp[k+1])\).
• Let \(k'\) be the smallest \(i\ (k < i)\) such that \(v_{i}=v_k\), then update \(dp[k] \leftarrow \min(dp[k],dp[k']+\sum_{i=k+1}^{k'}|v_k-v_i|)\).