Baltic Olympiad in Informatics, April 30 – May 3, 2010, Tartu, Estonia
Kristian works as a shopkeeper and sells candies. There are N packages in his shop and each of them may contain a different number of candies. When a customer comes and asks for K candies, Kristian has to bring some packages, such that the total number of candies in those packages is equal to K. If he is unable to do this, for example if someone asks for 4 candies and there are only 5 packages with 3 candies in each of them, often the customer gets upset and leaves.
Because of that, Kristian wanted to know how many different options he could provide to the next customer with the packages he currently has. He managed to solve this problem and now he is wondering what to do to improve the result. He wants to open one package and change the number of candies in it so that the total number of distinct options he can offer to the customer will increase as much as possible.
The first line of the text file candies.in contains one integer N (2 ≤ N ≤ 100). The second line contains a sequence of N integers Bi (1 ≤ Bi ≤ 7000) separated by single spaces and describing the numbers of candies in each package.
The first and only line of the text file candies.out should contain two integers P and Q separated by a single space. They mean that Kristian should take a package with P candies and change the number of candies in it to Q. P has to be equal to one of Bi. Since there can be many optimal results, output the one with P as small as possible. Among all results with the minimal P, choose the smallest possible Q. You can assume that Kristian can increase the total number of distinct orders he can serve by altering a single package.
| candies.in | candies.out | 4 1 3 4 4 | 4 9 |
With the packages described in the first sample input file, Kristian can serve orders of 9 different sizes, namely 1, 3, 4, 5, 7, 8, 9, 11 and 12. After changing a package with 4 candies to 9 candies, he could serve orders of size 1, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 16 and 17, which makes 13 distinct options in total.
| candies.in | candies.out | 5 3 3 3 3 3 | 3 1 |