Задача Wie

Байтазар - керівник бригади, яка шукає нафту. Відомо, що родовище нафти має вигляд відрізка з одним кінцем в точці А і іншим  всередині відрізку AB. Бригада з'ясувала, що в точці A нафта є, а в точці В - ні. Тепер Байтазару  потрібно знайти другу границю родовища  (де саме всередині відрізка AB кінець родовища). Оскільки в різних місцях  ґрунт  складається з різних порід, час буріння однієї свердловини залежить від  місця.  Бригада Байтазара невелика, тому вони не можуть бурити в різних місцях одночасно. Бос Байтазара бажає знати, коли бригада буде в змозі визначити межі родовища. Байтазар попросив вас про допомогу. Він розділив відрізок, що з'єднує точки А і В, на відрізки рівної довжини. Точка A має координату 0, точка B координату N+1, а між ними є N точок з координатами 1, 2. . ., N.  Байтазар повідомив вам кількість часу, необхідну для буріння свердловин у цих точках,- відповідно t₁, t₂. . ., t_N. Ви повинні створити такий план буріння, що час, необхідний  для визначення дальньої від точки A границі нафтового родовища, мінімальний (припускаючи щонайгірший сценарій).
Технічні умови. Програма повинна прочитати з клавіатури спочатку натуральне N (1<=N<=200), потім N натуральних чисел t₁, t₂. . ., t_N, розділених  пропусками (1<=t_i<=10⁶).  Програма повинна вивести на екран одне ціле число - найменшу кількість часу, який доведеться витратити Байтазару (припускаючи найгірший сценарій), аби визначити границі родовища.

Приклад
Введення:
4 8 24 12 6
Виведення:
42

Пояснення прикладу. Припустимо, що Байтазар бурить першу свердловину в точці 1, що вимагає часу 8. Якщо виявиться, що нафта там є, йому може знадобитися пробурити свердловини і в точці 2, і в точці 3. Якщо він пробурить лише в точці 3, може виявитися, що там нафти немає  і треба перевірити, чи є вона в точці 2. Якщо він пробурить лише в точці 2, може виявитися, що там нафта є, і треба перевірити точку 3. Таким чином, буріння свердловин може зайняти 8+24+12=44 одиниці часу. Виявляється, краще почати буріння з точки 2. Якщо виявиться, що нафти там немає, треба перевірити точку 1, отримаємо витрати часу 24+8=32. Якщо виявиться, що нафта там є, буде гарантовано досить пробурити в точках 3 і 4, отримавши сумарні витрати часу 24+12+6=42.