New Year's '16 P3 - Arithmetic Snowman - Olympiads Online Judge

New Year's '16 P3 - Arithmetic Snowman

Points: 5 (partial)

Time limit: 1.4s

Memory limit: 64M

Author:

Problem type

k_53P loves to build snowmen. But his favorite type has to be arithmetic snowmen. An arithmetic snowman consists of 3 snowballs whose sizes, when arranged in a non-decreasing order, form an arithmetic sequence. For example, k_53P can make an arithmetic snowman out of snowballs of sizes 1, 3, and 5.

The size of an arithmetic snowman is the sum of the sizes of the snowballs that it's made of. k_53P has made $N$ ~N~ snowballs of various sizes, find the largest arithmetic snowman he can make!

Constraints

Subtask 1 [50%]

$3 \le N \le 100$ ~3 \le N \le 100~

$1 \le size \le 100$ ~1 \le size \le 100~

Subtask 2 [50%]

$3 \le N \le 3000$ ~3 \le N \le 3000~

$1 \le size \le 10^5$ ~1 \le size \le 10^5~

Input Specification

The first line of input will contain $N$ ~N~, the number of snowballs.

The second line of input will contain $N$ ~N~ space-separated integers, the sizes of the snowballs.

Output Specification

One integer, the size of the largest arithmetic snowman k_53P can build. It is guaranteed that he can build at least one.

Sample Input

7
4 2 8 10 14 3 7

Sample Output

Explanation for Sample Output

k_53P will use the snowballs of sizes 2, 8, and 14 to make the snowman.

Comments

4

XIAOAGE commented on Jan. 1, 2016, 6:58 p.m. ← edited →

It says:

k_53P has made $N$ ~N~ snowballs of various sizes

But i think the sizes are repeated in batch #1

4

cheesecake commented on Jan. 1, 2016, 6:59 p.m.

Varying sizes does not imply that all sizes are distinct, sorry for the confusion.