资讯首页 热点资讯初中高中竞赛自招

文库 > 竞赛自招 > 正文

信息学竞赛测试题:列队

229 0 0 2019-05-20 10:56:43

题目描述

在llxy7刺杀了阿努比斯后,凤族的进攻被迟滞了。龙族的军队在Alyosha的带领下进行了反攻,并渐渐收回了失地。在若干年的僵持之后,大决战终于到来了。

高瞻远瞩的Alyosha早早地预见了这场决战的到来,为此,他早在几年以前就授意军师JosephWei开始进行准备。准备的一项内容就是要训练一些绝对的精锐部队。

JosephWei要训练的兵种有三种,我们将他们编号为1~3。在第一次列队时,他们的队形很混乱,也就是说,1~3这三种士兵在队列中是任意排列的。由于这些新兵根本不懂得如何列队,JosephWei无奈之下只能更改他们的兵种,使这些士兵的编号成为一个不升或不降的序列。比如编号序列1 3 2 1 2 3可以被变成3 2 2 1 1 1或 1 1 1 2 2 2或1 1 1 2 3 3。

现在JosephWei想知道他如何改变这些士兵的兵种才能让调整的次数最少。


输入格式

第1行:一个正整数N(1<=N<=30000),表示JosephWei要训练的士兵数。

第2..N+1行:每行一个1~3之间的正整数,表示这些士兵第一次列队时的编号。


输出格式

一行。一个正整数M,表示JosephWei需要调整的最小次数。


样例输入


5

1

3

2

1

1


样例输出


1

我要评论 0条评论

0/300

自律公约

网友评论

来第一个评论吧