Шарик и Матроскин чистят дорогу от снега. Дорога разделена на N участков. Для каждого участка известно, сколько минут нужно на его расчистку. Друзья договорились: Шарик чистит первые несколько участков с начала, а Матроскин — оставшиеся с конца. Нужно разделить работу так, чтобы максимальное время работы (у того, кто работает дольше) было минимальным.
Входные данные: В первой строке число N (2 ≤ N ≤ 1000). Во второй строке N положительных целых чисел, не превышающих 1000, — время расчистки каждого участка.
Выходные данные: Минимально возможное значение максимального времени работы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 3 4
|
6
|