问题描述

在一个美丽的0101小镇上，有一排整齐的 N 棵树。然而，最近这些树遭遇了虫子的困扰。经过环卫部门仔细调查，每棵树上都有着一定数量的虫子呢。现在，为了解决这个问题，小镇准备按排壹壹同学进行一场消杀行动。神奇的是，壹壹同学开着环卫车对一棵树进行消杀是瞬间完成的，并且能够一次性把这棵树上的虫子全部消灭掉。但是，消杀活动会对两边紧邻的树产生影响。如果那些树上有虫子，它们就会机灵地飞走逃避消杀，而且会飞得很远，不会停在任何一棵树上。那么，你能不能来帮助小镇制定一个完美的方案呢？让壹壹同学开着环卫车能够消灭掉尽可能多的虫子。快来和小镇的壹壹同学一起开启这场充满挑战的灭虫之旅吧。

输入

输入为一个数 N， 表示树的数量。 N课树对应的虫子数量

输出

最多消灭的虫子

样例

3 3 5 4

7

提示

假定只有3棵树，树上的虫子依次是：3 5 4，一眼看过去，消杀中间这棵，它虫子最多，但这会放走两边树上的一共7只虫子，不合理。换个思路，先消杀第三棵树上的四只虫子，就会放走中间树上的5只，但第一棵树上的三只虫子不会受影响，会被继续消杀掉，也就是总计消杀7只，放走5只。