Circular Table Seating Swap

You are given N people sitting around a circular table. Each person belongs to one of three factions. Your goal is to rearrange the seating such that all people belonging to the same faction sit together (i.e. in one contiguous block along the circle).

You may swap the positions of any two persons. Find the minimum number of swaps required so that people of the same faction are seated together.

The arrangement is circular, so the first and last persons are considered adjacent. The answer may be achieved by choosing an appropriate starting point on the circle and an optimal order of the three groups. In the final arrangement the order of the factions (for example, faction 1 first, then faction 2, then faction 3) can be chosen arbitrarily. Note that the minimal swap count for a particular grouping can be computed by counting the misplaced individuals in each segment and then using direct swaps and three‐cycle swaps. In particular, if in the segment intended for faction A there are some persons from faction B and in the segment intended for faction B there are some persons from faction A, they can be directly swapped. After taking all possible direct swaps, the remaining misplacements (which will occur in three‐cycles) can be fixed with two swaps each.

More formally, let the counts for the three factions be \(a, b, c\); for a given ordering \((A,B,C)\) and a chosen starting position, if the segments have lengths \(a, b, c\) respectively then let:

[ \text{mis}{A}^{B} = \text{number of faction }B\text{ in segment assigned to }A, \quad \text{mis}{A}^{C} = \text{number of faction }C\text{ in segment assigned to }A, \ \text{mis}{B}^{A} = \text{number of faction }A\text{ in segment assigned to }B, \quad \text{mis}{B}^{C} = \text{number of faction }C\text{ in segment assigned to }B, \ \text{mis}{C}^{A} = \text{number of faction }A\text{ in segment assigned to }C, \quad \text{mis}{C}^{B} = \text{number of faction }B\text{ in segment assigned to }C. ]

Then the number of direct swaps is given by:

[ D = \min(\text{mis}{A}^{B},,\text{mis}{B}^{A}) + \min(\text{mis}{A}^{C},,\text{mis}{C}^{A}) + \min(\text{mis}{B}^{C},,\text{mis}{C}^{B}). ]

If the total number of misplacements is \(T\), then after the direct swaps there remain \(T - 2D\) misplacements that form cycles. Each such cycle requires two swaps. Thus, the minimum number of swaps for this arrangement is:

[ \text{swaps} = D + 2 \times \frac{T - 2D}{3}. ]

Your task is to choose both an ordering (a permutation of the three factions) and a starting position on the circular table to minimize the total number of swaps.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10⁵), the number of people around the table.

The second line contains N integers, each being 1, 2, or 3, where the i-th integer denotes the faction of the i-th person in the given circular order.

outputFormat

Output a single integer, the minimum number of swaps required to group the same factions together.

sample

6
1 2 3 1 2 3

2