[USACO Oct07]奶牛饮水

Grade 0 Open Time Friday, 18 January 2013, 10:25 am
Discount 0.8 Time Discount Friday, 18 January 2013, 10:25 am
Allow late Yes Close Time Friday, 18 January 2013, 10:25 am
Input file privc.in Output file privc.out

译 by CmYkRgB123

Farmer John 的 N (1 <= N <= 1,000) 头奶牛中,每头奶牛的社会地位取决于她们的产奶量。她们的社会地位被指定为1,2或者3。当他们在井边排队喝水的事后,社会地位最高的(数值最小)的奶牛 排在前面。但是奶牛们总是忘掉自己的社会地位,除非Farmer John提醒,所以她们排队很乱。

因此,奶牛们必须通过两两交换位置达到规定的顺序。社会地位为1排在前,2的接着,3排在最后面。奶牛们通常是懒惰的,请你帮助算出所有奶牛一共至少交换几次位置,才能按顺序排列。

程序名: privc

输入

  • 第 1 行: 一个整数: N
  • 第 2..N+1 行: 每行一个整数,为奶牛i的社会地位。

输出

  • 第 1 行: 一个整数,至少交换的次数。

输入样例

9
2
2
1
3
3
3
2
3
1

输出样例

4

说明

2   2   2 < 1   1
2 < 1   1   1   1
1 < 2   2   2   2
3   3 < 2   2   2
3   3   3   3 < 2
3   3   3   3   3
2   2 < 3   3   3
3   3   3   3   3
1   1   1 < 2 < 3