Minimum Card Changes for Proper Grouping

The cows are a bit silly about their dinner partners. They line up with cards marked with numbers 1, 2, or 3, but the order is mixed up. Farmer John can change some of these numbers (by rewriting a cow's card) without rearranging the cows. His goal is to achieve a grouping that is either in ascending order (all 1's, then 2's, then 3's) or descending order (all 3's, then 2's, then 1's).

Formally, given a sequence \(a_1,a_2,\dots,a_N\) with \(1 \le a_i \le 3\), you need to change the minimum number of values so that the resulting sequence can be partitioned into at most three consecutive segments where all the values in the first segment are equal to \(x\), in the second segment equal to \(y\), and in the third segment equal to \(z\) with either \((x,y,z)=(1,2,3)\) or \((x,y,z)=(3,2,1)\). Note that some segments may be empty.

Your task is to compute the minimum number of card changes required.

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 30000\)), the number of cows.

The second line contains \(N\) integers \(a_1,a_2,\dots,a_N\) with each \(a_i\) in {1,2,3} representing the cow's current card.

outputFormat

Print a single integer representing the minimum number of card changes required.

sample

5
1 1 2 2 3

0