По кругу и обратно

Числа расставлены по кругу. Найдите наибольшую сумму непустого куска из подряд идущих по кругу элементов, беря каждый элемент не более одного раза.

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Одно число.