Отрезок по кругу

Числа расставлены по кругу: после последнего снова идёт первый.

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

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

Одно число.

Ответ бывает двух видов: обычный кусок или кусок, перескакивающий через край. Второй — это весь ряд без какого-то куска внутри, и чтобы он был как можно больше, выброшенный кусок должен быть как можно меньше. Отдельно продумайте случай, когда все числа отрицательные.