타일 밟기

경시장으로 가는 길에, 자연수가 하나씩 적힌 타일이 한 줄로 놓여 있다. 타일에 적힌 수들은 모두 서로 다르며, 줄의 처음부터 끝까지 증가하는 순서로 놓여 있다.

철수는 이 타일들 중 하나에서 출발하여, 몇 개의 타일을 밟으며 경시장으로 가려고 한다. 이때 밟는 타일에 적힌 수들이 일정한 자연수 $d$($d \ge 1$)만큼씩 커지도록 밟는다. 즉, 밟는 수들은 공차가 $d$인 등차수열을 이루어야 한다.

출발하는 타일과 공차 $d$를 어떻게 고르느냐에 따라 연속해서 밟을 수 있는 타일의 개수가 달라진다. 철수는 이렇게 밟은 타일에 적힌 수들의 합 중 최댓값이 얼마인지 알고 싶어 한다. 단, 연속해서 밟는 타일은 적어도 $3$개 이상이어야 한다.

예를 들어 타일에 적힌 수들이 다음과 같다고 하자.

1, 2, 6, 7, 11, 12, 13, 15, 17, 20, 23

이때 $3$개 이상 연속해서 밟을 수 있는 모든 경우는 다음 표와 같다.

이 중 합이 가장 큰 경우는 $17, 20, 23$($d = 3$)이며, 그 합은 $60$이다.

타일에 적힌 수들이 증가하는 순서로 주어질 때, 위와 같은 방법으로 $3$개 이상 연속해서 밟을 수 있는 타일에 적힌 수들의 합 중 최댓값을 구하는 프로그램을 작성하여라. $3$개 이상 연속해서 밟을 수 있는 경우가 존재하지 않으면 $0$을 출력한다.

첫째 줄에 타일의 개수 $N$이 주어진다. ($3 \le N \le 3\,000$)

둘째 줄에 $N$개의 타일에 적힌 자연수가 증가하는 순서로 공백으로 구분되어 주어진다. 각 수는 $1\,000\,000$ 이하이며, 모두 서로 다르다.

$3$개 이상 연속해서 밟을 수 있는 타일이 존재하면, 그렇게 밟은 타일에 적힌 수들의 합 중 최댓값을 첫째 줄에 출력한다. 그러한 경우가 존재하지 않으면 $0$을 출력한다.