Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K
1, K
2, ..., K
N этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?
Входные данные
В первой строке содержится число N – количество альбомов. Во второй строке идет N чисел K
1, K
2, ..., K
N, задающих вместимости альбомов. N – натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.
Выходные данные
Выведите сначала число E – максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел – каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
Примеры
№ | Входные данные | Выходные данные |
1
|
4 1 2 1 1
|
2
|