На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить такую максимальную сумму элементов пары, чтобы суммы элементов пары и их индексов были кратны 3. Если такой суммы не найдется, вывести «–1». Нумерация элементов начинается с 1.
Напишите эффективную по памяти и времени программу.
Входные данные
В первой строке входных данных задаётся количество чисел
N (1 <
N <=100000). В каждой из последующих
N строк записано одно натуральное число, не превышающее 10000.
Выходные данные
В качестве результата программа должна вывести одно число: максимальную сумму пары кратную трём с суммой индексов кратной трём или «
–1», если такой пары не нашлось.
Примеры
| № |
Входные данные |
Выходные данные |
Комментарий |
| 1 |
10
1 2 3 4 5 6 7 8 9 10
|
18 |
найденная пара: (a[8]=8; a[10]=10) |
| 2 |
23
36 16 15 15 17 16 14 15 47 22 27 29 35 23 39 29 15
25 16 35 28 45 26
|
75 |
найденная пара: (a[9]=47; a[21]=28) |
Примечание: в примерах элементы массива располагаются в одну строчку для экономии места и улучшения читабельности. В самих тестах к задаче все эелементы расположены по одному числу в строке.