The sum is a multiple of three
Problem
The input of the program is a sequence of N positive integers. All pairs of different elements of the sequence are considered (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is unimportant). It is necessary to determine the maximum sum of the elements of a pair so that the sums of the elements of the pair and their indices are a multiple of 3. If such a sum is not found, output "–1". Element numbering starts from 1.
Write a memory and time efficient program.
Input
The first line of the input specifies the number of numbers
N (
\(1 < N <= 100000\)). Each of the following
N lines contains one natural number not exceeding 10000.
Imprint
As a result, the program should output one number: the maximum sum of a pair that is a multiple of three with the sum of the indices that is a multiple of three, or "
–1" if no such pair was found.
Examples
| # |
Input |
Output |
Comment |
| 1 |
10
1 2 3 4 5 6 7 8 9 10
|
18 |
found pair: (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 |
pair found: (a[9]=47; a[21]=28) |
Note: in the examples, array elements are placed on a single line to save space and improve readability. In the tests themselves for the task, all elements are located one number per line.