14931번 - 물수제비 (SUJEBI)

문제

급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리, 환경부 장관은 물론 26부의 장관 및 차관이 모여 열띤 토론을 벌였다. 많은 좋은 의견이 나왔지만 그 중 단 한 계획만이 만장일치로 통과되었으니 일명 Flat Dumpling Plan (수제비 계획)으로, 강에서 돌로 물수제비를 해 여러 생태계 교란종을 맞춰 죽이는 계획이었다. 계획을 이행할 강의 강폭은 L(1 ≤ L ≤1,000,000)로 강을 L개의 연속한 칸으로 모델링할 수 있다. 환경부에서는 강의 1번 칸, 2번 칸, … L번 칸 각각에 살고 있는 생태계 교란종의 치명도에 따라 점수를 매겨 놨다. (고유종이 서식하는 곳도 있으므로 점수가 음수일 수도 있다.) 돌을 두 개 이상 던지기에는 팔이 아팠기에 오직 돌 하나로만 진행하기로 했다. 던져진 돌은 던진 파워에 따라서 일정 간격 d(1≤d≤L)로 뛴다. 즉, d번 칸, 2d번 칸, … [L/d]d번 칸을 지난다. 돌이 거친 칸들의 점수의 합을 최대로 하는 자연수 d를 찾아 정부에 보고하자.

입력

첫째 줄에 강폭 L이 주어진다.

둘째 줄에는 L개 칸의 점수가 주어진다. 모든 점수는 -50,000 이상 50,000 이하의 정수이다.

출력

점수를 최대로 하는 d 값과 그 때의 점수를 공백을 사이에 두고 출력한다. 만약 점수를 최대로 하는 d가 여럿 존재할 경우 가장 작은 d를 출력한다. 최대의 점수가 0 이하인 경우에는 계획을 시행하지 않는 것이 나으므로 0 0을 출력한다.

제한

힌트