You are given a sequence
N of positive integers. All pairs of elements of the sequence are considered, located at a distance of at least 8 from each other (the difference in the indices of the elements must be 8 or more). It is necessary to determine the maximum sum of such a pair.
Write a time and memory efficient program to solve this problem.
Input
The first line of the input specifies the number of numbers
N (
\(9 <= N <= 100000\)). Each of the following
N lines contains one natural number not exceeding 10000.
Input
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
10
1
3
5
4
6
7
9
10
12
11 |
14 |
Explanation. From 10 numbers, you can make 3 pairs that satisfy the condition. These will be elements with indices 1 and 9, 1 and 10, 2 and 10. For a given set of numbers, we get pairs (1, 12), (1, 11), (3, 11). The maximum sum of numbers in these pairs is 14.