#90. 整理书架

整理书架

样例下载

题目描述

学校阅览室的书架上放着一排书,有语文书、数学书、英语书。这些书被同学们归还后杂乱地放在书架上。

小 A 想要把书架整理一下,他希望语文书全部排放在最前面,数学书全部排放在中间,英语书全部排放在最后面。

他每次可以交换任意两本书。问:至少需要多少次交换可以将书本排好?

输入格式

第一行:一个整数 n,表示书本的数量。

接下来 n 行,每行一个整数,用来描述初始时从前向后依次摆放的书本类型。保证每个整数都是 1, 2, 3 中的其中一个,其中 1 表示语文书,2 表示数学书,3表示英语书。

输出格式

一个整数,表示将书本排好的最少交换次数。

样例输入

5
2
1
1
3
2

样例输出

2

数据范围

20% 的数据,1 ≤ n ≤ 10。

40% 的数据,1 ≤ n ≤ 1,000。

70% 的数据,1 ≤ n ≤ 1,000,000。

100% 的数据,1 ≤ n ≤ 10,000,000。