Nauw có một dãy ~a~ gồm ~n~ phần tử phân biệt: ~a_1, a_2, a_3, \ldots, a_n~.

Tìm tổng ~a_i+a_j+a_k~ lớn nhất sao cho:

• ~1 \le i < j < k \le n~.

• ~a_i < a_j < a_k~.

Nếu như không tồn tại ~i, j, k~ thỏa mãn thì in ra ~-1~. Hãy giúp Nauw giải quyết bài toán này nhé!

Input

• Dòng đầu tiên ghi một số nguyên ~n~ là số phần tử của dãy ~a~ (~3 \le n \le 5000~).

• Dòng thứ hai ghi ~n~ số nguyên dương phân biệt mô tả dãy ~a~ (~1\le a_i \le 10^5~).

Output

• In ra một số nguyên dương duy nhất là kết quả của bài hoặc in ra ~-1~ nếu như không có đáp án.

Scoring

Sample Input 1

7
1 5 2 3 4 9 6

Sample Output 1

16

Notes

Giá trị tốt nhất đạt được khi ~i=4, j=5, k=6~, và tổng là ~a_i + a_j + a_k = 3 + 4 + 9 = 16~.