Дано масив \(A\) із \(N\) цілих чисел, розташованих по колу - після \(N\)-го елемента іде перший.

Ваше завдання --- знайти максимальну суму безперервного підмасиву.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\).

Наступний рядок містить \(N\) цілих чисел \(A_i\).

Числа у рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести отриману суму.

Обмеження

\(1 \le N \le 10^6\)

\(-10^6 \le A_i \le 10^6\)

Приклад вхідних даних

8
10 -3 -4 7 6 5 -4 -1

Приклад вихідних даних

23