Дана последовательность
N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 8 друг от друга (разница в индексах элементов должна быть 8 или более). Необходимо определить максимальную сумму такой пары.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Входные данные
В первой строке входных данных задаётся количество чисел
N (
\(9 <= N <= 100000\)). В каждой из последующих
N строк записано одно натуральное число, не превышающее 10000.
Входные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10
1
3
5
4
6
7
9
10
12
11 |
14 |
Пояснение. Из 10 чисел можно составить 3 пары, удовлетворяющие условию. Это будут элементы с индексами 1 и 9, 1 и 10, 2 и 10. Для заданного набора чисел получаем пары (1, 12), (1, 11), (3, 11). Максимальная сумма чисел в этих парах равна 14.