//
// Created by 21122 on 2022/5/28/0028.
//
#include<iostream>
#include<algorithm>
#include<cstring>
//#include<bits/stdc++.h>
using namespace std;

int r[100010];
int n;
int left_arr[100010];
int right_arr[100010];


bool is_okay(int p_nums)
{   //第一个位置是特殊情况，提前处理
    int a = r[1], b = p_nums - r[1];
    left_arr[1] = a;
    right_arr[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        if(i % 2 == 0)
        {   // 偶数，从右边开始拿
            right_arr[i] = min(b - right_arr[i - 1], r[i]);
            left_arr[i] = r[i] - right_arr[i];
        }
        else
        {   // 为奇数，从左边开始拿
            left_arr[i] = min(a - left_arr[i - 1], r[i]);
            right_arr[i] = r[i] - left_arr[i];
        }
    }

    if(left_arr[n] == 0)
    {
        return true;
    }
    return false;


}


int main()
{
    int n;
    while(true)
    {
        cin >> n;
        if(n == 0)
        {
            break;
        }
        memset(r, 0, sizeof r);
        memset(left_arr, 0, sizeof left_arr);
        memset(right_arr, 0, sizeof right_arr);
        int least = 0;
        for(int i = 1; i <= n; i++)
        {
            cin >>r[i];
            least = max(least , r[i] + r[i - 1] );
        }
        if(n == 1)
        {   //特判
            cout << r[1] << endl;
            continue;
        }

        //便于后续的比较过程，
        r[n + 1] = r[1];
        least = max(least, r[1] + r[n]);


        int L = least;
        int R = 3000005;
        //二分查找合适的礼物个数
        if(n % 2 == 1)
        {
            while(L < R)
            {
                int M = (L + R) / 2;
                //int M = L + (R - L) / 2;
                if(is_okay(M))
                {
                    R = M;
                }
                else
                {
                    L = M + 1;
                }

            }
        }

        cout << L << endl;
    }


    return 0;
}

//
// Created by 21122 on 2022/5/28/0028.
//
#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>

using namespace std;

int arr[2000010];


int main()
{
    ios::sync_with_stdio(0);
    int n;
    while(cin >> n)
    {
        if(n == 0)
        {
            break;
        }
        for(int i = 1; i <=n ; i++)
        {
            cin >> arr[i];
        }
        std::sort(arr + 1, arr + 1 + n);
        // 防止格式错误；
        cout << arr[1];

        for(int i = 2; i <= n ; i++)
        {
            cout << " " << arr[i];
        }
        cout << endl;
    }

    return 0;

}