Problem1552--VIJOS-P1339

1552: VIJOS-P1339

Time Limit: 0 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

在潘帕斯草原上牛甚多,他们统治着草原的中心部分,鹰的领地环绕着牛所在的地方,而且每个鹰都有一片自己的领地。在@潘帕斯雄鹰将羽毛进行染色后,其他的鹰纷纷效仿,也想把自己的羽毛染成五颜六色。但是问题随之而来,相邻的两个鹰(1和2相邻,1和n也是相邻的)如果发现对方身上有和自己有一样颜色的羽毛就会和对方进行一场你死我活的空中战斗。为了避免这种情况必须要想一种办法才行。由于@潘帕斯雄鹰是第一个将羽毛进行染色的鹰,他被鹰们指派去买颜料(自费T_T),买颜料当然是要花钱的。@潘帕斯雄鹰想尽量的少买颜料。他发现由于各个鹰的喜好不同,他们想在身上染的颜色种类的个数也是不一样的,有些鹰喜欢把自己的羽毛涂的颜色多些,有些则少。通过统计得出了第i个鹰想在自己身上涂Ai种颜色。你现在的任务是维护世界和平找到最少的颜色种类使得每个相邻的鹰身上的羽毛颜色都可以没有相同的。

Input

第一行n(1< =n< =20000) 第二行开始每行有一个数ai(1< =ai< =100000)表示第i个鹰要在身上涂ai种颜色

Output

一个数,即最少的满足条件的颜色种类

Sample Input Copy

4
2
2
1
1

Sample Output Copy

4