Stacked Pillars Plate Sorting

You are given three pillars, labeled \(A\), \(B\), and \(C\). Initially, pillar \(A\) contains \(N\) plates and pillars \(B\) and \(C\) are empty. Each plate belongs to one of three types: \(1\), \(2\) or \(3\). You are allowed to perform the following move: remove the top plate from any pillar and place it on top of another pillar.

The goal is to arrange the plates so that all plates of type \(1\) end up in pillar \(A\), all plates of type \(2\) end up in pillar \(B\), and all plates of type \(3\) end up in pillar \(C\). Note that in the final configuration, the order of the plates on each pillar does not matter.

Initially, all \(N\) plates are in pillar \(A\) in a given order. The input sequence lists the plates from bottom to top of pillar \(A\). Even if a plate is already on its target pillar (for example, a \(1\) in pillar \(A\)), if it blocks a plate that needs to be moved from below, extra moves are required (i.e. you might need to temporarily remove it and later restore it).

An optimal strategy can be derived using the following idea. Suppose the input sequence (from bottom to top) is \(a_0, a_1, \dots, a_{N-1}\). Let \(\text{nonOne}\) be the number of plates which are not of type \(1\). If there is at least one plate which is not \(1\), let \(p\) be the index of the first plate (from the bottom) such that \(a_p \neq 1\). Then, all plates of type \(1\) that appear above index \(p\) are blocking access to the misplaced plates and will have to be removed and then restored. Thus, if we let \(cnt\) be the number of plates \(a_i=1\) for \(i > p\), then the minimum number of moves required is given by \[ \text{moves} = \text{nonOne} + 2 \times cnt. \] If all plates are of type \(1\) then no moves are needed.

inputFormat

The first line contains an integer \(N\) \((1 \le N \le 10^5)\), the number of plates.

The second line contains \(N\) space-separated integers \(a_0, a_1, \dots, a_{N-1}\) (each is \(1\), \(2\), or \(3\)), representing the plates from the bottom to the top of pillar \(A\).

outputFormat

Output a single integer, the minimum number of moves required to achieve the goal configuration.

sample

3
1 1 1

0