Stop Counting!
시간 제한7초메모리 제한1024 MB
정수 카드 덱이 주어질 때, 한 개의 연속 구간을 건너뛰어 남은 카드 평균이 최대가 되도록 하는 값을 구한다.
문제
마틴게일 카지노는 기존 게임에 싫증난 도박꾼을 끌어들이기 위해 새로운 게임을 만들고 있다. 그중 하나가 빠른 템포로 진행되는 운 게임 Stop Counting!이다. 한 손님이 카드 덱을 가진 딜러와 게임을 한다. 각 카드에는 정수 값이 적혀 있다.
딜러는 덱의 카드를 순서대로 하나씩 공개하며, 지금까지 공개한 카드의 합과 장수를 기록한다. 어떤 카드를 내기 전에 플레이어는 "Stop Counting!"을 외칠 수 있다. 그러면 딜러는 계속 카드를 순서대로 공개하지만, 그 카드들을 누적 합에 넣지 않는다. "Stop Counting!"을 외친 뒤 어떤 카드를 내기 직전에 플레이어는 "Start Counting!"을 외칠 수도 있고, 그러면 딜러는 이후 카드부터 누적 합에 다시 포함한다. 플레이어는 "Stop Counting!"과 "Start Counting!"을 각각 최대 한 번씩만 외칠 수 있고, "Start Counting!"을 외치려면 먼저 "Stop Counting!"을 외쳐야 한다. 카드가 "셈에 포함된다"는 것은 플레이어가 "Stop Counting!"을 외치기 전에 나온 카드이거나 "Start Counting!"을 외친 뒤에 나온 카드라는 뜻이다.
게임의 상금은 셈에 포함된 카드 값의 평균이다. 즉, 셈에 포함된 카드 값의 합을 셈에 포함된 카드 수로 나눈 값이다. 셈에 포함된 카드가 없으면 상금은 0이다.
당신은 딜러와 내통하고 있어서 덱 전체를 순서대로 미리 알고 있다. 얻을 수 있는 최대 상금은 얼마인가?
입력
입력의 첫 줄에 정수 1 ≤ N ≤ 1 000 000이 주어진다. 이는 덱에 있는 카드 수이다.
입력의 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 이는 카드에 적힌 값이다. 각 카드의 값은 [−109, 109] 범위에 있다. 카드는 입력에 주어진 순서대로 나온다.
출력
얻을 수 있는 가장 큰 상금을 출력한다. 절대 오차가 10−6 미만이거나 상대 오차가 10−9 미만이면 정답으로 간주한다.
힌트
첫 번째 예시에서는 −10 앞에서 "Stop Counting!"을 외치고 마지막 10 앞에서 "Start Counting!"을 외치면, 셈에 포함된 카드로 평균 10.0을 얻을 수 있다.
두 번째 예시에서는 모든 값이 음수이므로, 첫 카드가 나오기 전에 "Stop Counting!"을 외치고 마지막 카드가 나온 뒤에 "Start Counting!"을 외치는 것이 최선이다. 셈에 포함된 카드가 없으므로 셈에 포함된 카드의 평균은 0.0이다.