题目描述
在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需要调整的最小次数。
样例输入
样例输出