오늘도 비가 오고 있습니다. Paweł과 Gaweł은 집에 머물 수밖에 없었습니다. 수업이 없기 때문에 그들은 게임을 만들기로 결정했습니다.
Paweł은 기발한 아이디어를 가지고 있었습니다.
그는 한 장의 종이에 n개의 칸을 그렸습니다. 각 칸에는 두 개의 숫자가 있습니다. 첫 번째는 칸 번호(1에서 n까지의 자연수, 각 칸은 서로 다른 숫자를 가짐)이고 두 번째는 칸의 값(-1,000에서 1,000 사이의 정수)입니다.
플레이어는 1에서 6까지의 숫자가 적힌 정육면체 주사위를 던지고, 주사위에서 나온 수만큼 말을 움직입니다. 말은 칸 번호 1에서 시작하여 칸 번호 n에 도착하면 게임이 종료됩니다. 플레이어가 얻는 점수는 말이 지나온 칸 값의 합입니다.
몇 게임을 플레이한 후 Paweł과 Gaweł은 여러 가지 다른 결과를 얻었지만 그 중 어떤 것이 가능한 한 가장 큰 점수가 되는 것인지는 알 수 없었습니다. 그래서 그들은 유능한 프로그래머인 당신에게 주어진 보드에 대해 가능한 최대 점수를 계산할 프로그램을 작성하도록 요청했습니다.
입력
입력의 첫 번째 줄에는 보드의 칸 수를 나타내는 하나의 정수 n(1 ≤ n ≤ 10^6)이 주어집니다.
두 번째 줄에는 n개의 정수 w1, w2, ..., wi(-1,000 ≤ wi ≤ 1,000)가 포함됩니다. 여기서 wi는 i번째 칸의 값을 나타냅니다.
coffee21 4년 전
문제
오늘도 비가 오고 있습니다. Paweł과 Gaweł은 집에 머물 수밖에 없었습니다. 수업이 없기 때문에 그들은 게임을 만들기로 결정했습니다. Paweł은 기발한 아이디어를 가지고 있었습니다.
그는 한 장의 종이에 n개의 칸을 그렸습니다. 각 칸에는 두 개의 숫자가 있습니다. 첫 번째는 칸 번호(1에서 n까지의 자연수, 각 칸은 서로 다른 숫자를 가짐)이고 두 번째는 칸의 값(-1,000에서 1,000 사이의 정수)입니다.
플레이어는 1에서 6까지의 숫자가 적힌 정육면체 주사위를 던지고, 주사위에서 나온 수만큼 말을 움직입니다. 말은 칸 번호 1에서 시작하여 칸 번호 n에 도착하면 게임이 종료됩니다. 플레이어가 얻는 점수는 말이 지나온 칸 값의 합입니다.
몇 게임을 플레이한 후 Paweł과 Gaweł은 여러 가지 다른 결과를 얻었지만 그 중 어떤 것이 가능한 한 가장 큰 점수가 되는 것인지는 알 수 없었습니다. 그래서 그들은 유능한 프로그래머인 당신에게 주어진 보드에 대해 가능한 최대 점수를 계산할 프로그램을 작성하도록 요청했습니다.
입력
입력의 첫 번째 줄에는 보드의 칸 수를 나타내는 하나의 정수 n(1 ≤ n ≤ 10^6)이 주어집니다. 두 번째 줄에는 n개의 정수 w1, w2, ..., wi(-1,000 ≤ wi ≤ 1,000)가 포함됩니다. 여기서 wi는 i번째 칸의 값을 나타냅니다.
출력
출력의 첫 번째 줄에는 주어진 보드에서 가능한 최대 점수를 출력합니다.
예제 입력1
4
1 2 -1 1
예제 출력1
4