Description
北京城曾经被四层城墙包围着：紫禁城墙、皇城城墙、内城城墙、外城城墙，在五六十年代的时候，其中的很多城墙因为要建设道路而被拆掉了。城墙曾经被很多的守卫保护着，守卫们住在守卫亭里面。整个城墙可以被看做是一个大大的圏，每个守卫都有两个邻居。守卫们每天都需要再自己的岗亭中，守卫好各自的职责城墙，所以工作起来非常的枯燥，因此如何调动守卫们的工作积极性非常重要。为了能够更好地调动守卫们的积极性，相关部门设立了很多不同奖项:杰出工作奖、最佳守护奖、最佳视力奖等等。
一个奖可以颁发给多个守卫，一个守卫也可以得到多个奖项，但是相同的奖项不能颁给相邻的两个守卫。
你的任务就是编写一个程序，计算出一共需要多少种奖项？
Input
输入包含多组测试数据。
每组测试数据：
第一行是一个整数n，表示守卫的总数（1≤n≤100000）
接下来n行，每行一个整数，表示第i个守卫需要ri个不同的奖项（1≤ri≤100000）。注意相邻的两个守卫的奖项不能相同，第一个守卫和最后一个守卫也是邻居。
当输入为“0”时，表示输入结束。
Output
对于每组测试数据，输出一行，一个整数，表示一共需要的最少的奖项的种类数。（每个守卫一种奖项只能有一个，一种奖项不能颁给相邻的两个守卫）
3
4
2
2
5
2
2
2
2
2
5
1
1
1
1
1
0