Arranging Shapes

Time limit1sMemory limit128 MB

Summary

Given a sequence of three shape types, compute the minimum swaps needed to group each type into one contiguous block, in any order of blocks.

Level: Medium6 of 10
Topics: Sliding window, Greedy, Array
Solved: No attempts yet

Problem

Triangles, squares, and circles are arranged in a line. In one operation, choose any two positions and swap the shapes at those positions. The goal is to rearrange the line so that each kind of shape occupies one contiguous block. The order of the three blocks does not matter.

Given the current order of the shapes, write a program that finds the minimum number of swaps needed to make equal shapes contiguous.

Input

The first line contains the total number of shapes $N$ . $N$ is between $3$ and $100,000$ , inclusive.

The second line contains $N$ integers separated by spaces, representing the shapes in order. Integer $1$ represents a triangle, integer $2$ represents a square, and integer $3$ represents a circle.

Each of the three kinds of shape appears at least once.

Output

Print the minimum number of swaps required to make equal shapes contiguous.

Examples1

Example 1
Input
```
8
1 3 3 2 1 1 3 2
```
Expected output
```
2
```