#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。