背景

阿邦是一名经验丰富的果园害虫消杀专家。趁着夜幕降临，阿邦计划今晚对果园里的一系列果树进行虫害消杀。

问题描述

环形果园里按环形顺序种了 N 棵果树（由于是环形的，所以位置1和位置n的树是相邻），每棵树上都有一定数量的害虫。阿邦说对一颗树消杀是瞬间完成的，而且能将这个树上的虫子全部消灭，但是会对相邻的两颗树的虫子有影响，两颗树的上虫子会逃走，飞到很远的地方，不会停到任何一颗树上，从而影响消杀的效果。 作为一向细致且谨慎的害虫管理专家，阿邦希望消杀的效果最好。他想知道，他今晚最多可以消杀多少害虫？

输入

共两行，第一行是一个整数N(1≤N≤1,000) ，表示一共有N颗果树。 第二行是N个被空格分开的正整数，表示每一颗果树上的害虫数量。每颗果树上的害虫数量均不超过1000。

输出

一个整数，表示阿邦在不惊扰相邻树上害虫的情况下，最多可以消杀害虫的数量。

样例

3
2 3 2

3

说明：你不能先消杀第一颗树的虫子，然后消杀第三颗树的虫子, 因为他们是相邻的。

Limitation

1s, 1024KiB for each test case.