First of all, consider reversing the whole process: we have $1\sim n$ in order on pillar $B$ at the beginning, and we need to move them to $A$ arranged in the given order $p$.

Now consider $p_1$. We can see that:

• at some moment, $p_1$ is moved from the top of $B$ or $C$ to the bottom of $A$.
• before this move, $A$ must be empty, and $B$ and $C$ are complementary subsequences of $1\sim n$.
• before this move, $p_1$ must be located at the top of one of $B$ and $C$, and all disks $ < p_1$ must be located at the other pillar.
• after this move, $p_1$ is put in place and no longer operated as there's no need to do so, otherwise the solution won't be optimal.

Then we can ignore $p_1$ and continue processing $p_2$, then $p_3$, and so on, following the same logic.

Therefore, we only care about the states, i.e. the complementary subsequences in each iteration. In order to transit between states, we can see that the feasible operational methods are actually very restricted. The only optimal type of operation is as follows:

• let the largest disk that needs to be changed to the opposite pillar (from $B$ to $C$ or from $C$ to $B$) be $x$.
• move $1\sim(x-1)$ to $A$, one by one.
• move $x$ to the opposite pillar.
• move $(x-1)\sim 1$ one by one to $B$ or $C$ as you wish.
• the number of moves is $2x-1$ (assuming $1\sim x$ are all still present).

Now let's go back and consider $p_1$. At the moment the best solution is to operate $x=p_1-1$ disks, but this may not be the desired optimal state as there is potential to facilitate future iterations by operating more disks.

We can record the best operations for now, and extend them afterwards when we find it possible to optimize and facilitate the current iteration.

Whenever we make an operation with $x=t$, all previous operations with $x < t$ will no longer be useful. Therefore, the records can be maintained with a monotonic stack, where the nodes closer to the top of the stack has smaller $x$ and more recent operation times. Additionally, we need to keep track of non-trivial disks which are located at the opposite pillar to the disk above them.

Specifically, let the node struct consist of 3 variables, $\{pos,optpos,diff\}$:

• $pos$ is the position of the referred disk from bottom to top in all present disks.
• $optpos$ is the position (from bottom to top) reached by the corresponding operation, related to the referred disk. In other words, the corresponding operation affected all disks at and above $optpos$.
• $diff\in\{true,false\}$ means whether the disk at $pos$ and $pos+1$ are located on different pillars (i.e. whether one of them is located at $B$ and the other one is located at $C$).

Now I'll describe the specific process of the algorithm. Assuming we're in the $i$-th operation, where $p_1,p_2,\ldots,p_{i-1}$ have all been put in place, and we need to put $p_i$ in place. Therefore, let the number of present disks be $m=n-i+1$. Let $pos$ be the position of $p_i$ from bottom to top (this can be calculated with a simple fenwick tree). Initialize $optpos:=\infty$ and $cost:=0$.

• pop the top node $nd$ that satisfies $nd.pos>pos$ one by one. For each popped $nd$:

  • if $nd.diff=true$, i.e. the disk above the referred disk is located at the opposite pillar, we need to make them located at the same pillar. We either extend an operation to $nd.pos$, with $cost:=cost+2\times(\min\{optpos,nd.optpos\}-nd.pos)$; or reinitiate an operation, with $cost:=\max\{0,2\times(m-nd.pos)-1\}$. We pick the one with smaller cost. Finally, let $optpos:=nd.pos$.
  • if $nd.diff=false$, let $optpos:=\min\{optpos,nd.optpos\}$.

• after stack popping, if the top node has $nd.pos=pos$, we need to handle this node specially, since now we need to make the disks at $pos$ and $pos+1$ located at different pillars instead of the same pillar.

  • if $nd.diff=true$, let $optpos:=\min\{optpos,nd.optpos\}$.
  • if $nd.diff=false$, let $cost:=cost+2\times(\min\{optpos,nd.optpos\}-nd.pos)$ or $cost:=\max\{0,2\times(m-nd.pos)-1\}$, and $optpos:=nd.pos$.
  • this node is also popped.

• if the top node has $nd.pos< pos$, or that the stack is empty, we still need to do something to make the disks at $pos$ and $pos+1$ located at different pillars. Let $cost:=\min\left\{cost+2\times(optpos-pos),\max\{0,2\times(i-pos)-1\}\right\}$ and $optpos:=pos$.

• after all above procedures, finally we need to push a node $\{pos-1,optpos,true\}$ onto the stack. However, if there is already a node with $nd.pos=pos-1$ at the top of the stack, then we need to do $nd.optpos:=\min\{nd.optpos,optpos\}$ and $nd.diff:=\neg nd.diff$.

The answer is $n+\sum_i cost$.