Башенки из кубиков
(Время: 2 сек. Память: 64 Мб Сложность: 42%)
Маленький Рома любит играть в кубики и строить из них башенки. Всего у него N кубиков, каждый из которых определяется целочисленным размером Ai, который определяет длину ребра i-го кубика. Если поставить несколько кубиков последовательно друг на друга, то получается башенка.
Рома считает башенку красивой, если каждый последующий сверху вниз кубик имеет размер на единицу больше, чем предыдущий. Высота башенки – это количество кубиков в ней. То есть для красивой башенки высоты M, состоящей из кубиков с размерами S1, S2, …, SM, должно выполняться условие: Si-1 = Si – 1 для i от 2 до M.
Рома хочет для построения башенок использовать все кубики. Он заметил, что чем меньше в результате получается красивых башенок при одном и том же наборе кубиков, тем выше в среднем получаются башенки. Однако, кубиков у Ромы очень много и у него не получается минимизировать число красивых башенок так, чтобы в результате построения были использованы все кубики.
Помогите Роме с этой задачей!
Входные данные
Первая строка входного файла INPUT.TXT содержит число N – количество кубиков у Ромы (1 ≤ N ≤ 2×105). Во второй строке содержатся N целых чисел A1, A2, …, AN , где Ai – размер i-го кубика (1 ≤ Ai ≤ 2×105).
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число K – минимальное количество красивых башенок, которые можно построить из имеющихся кубиков.
В следующих K строках выведите описание башенок по одному описанию башенки в каждой отдельной строке. Описание башенки состоит из двух целых чисел, где первое число – размер самого маленького (верхнего) кубика в башенке, а второе число – размер самого большого (нижнего) кубика в башенке.
Если существует несколько решений задачи, выведите любое из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2 3 | 1
1 3 |
| 2 | 5
6 2 3 2 1 | 3
1 3
2 2
6 6 |
Система оценки
Решения, работающие только для N ≤ 100, будут оцениваться в 40 баллов.
Решения, работающие только в тех случаях, когда размеры всех кубиков различны, будут оцениваться в 40 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
