Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 32 Mb

Ответы на вопросы

Задача: Шахматы

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один  горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку,  соответственно.

Сегодня на шахматном кружке занятие было посвящено ладейным окончаниям, и Васю заинтересовал вопрос: как расставить минимальное число ладей на его доске так, чтобы каждую клетку поля била хотя бы одна ладья. Ладья бьет те клетки, которые расположены с ней на одной вертикали или одной горизонтали. Помогите Васе расставить на его доске минимальное число ладей требуемым образом.

Формат входных данных
В первой строке входного файла задано целое число n — количество столбцов доски
(1 ≤ n ≤ 1000). Следущая строка содержит n чисел a1, a2, . . . , an — количество клеток в столбцах
(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).

Формат выходных данных
В первой строке выведите число k — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие k строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.
Если подходящих расстановок несколько, можно вывести любую.

Примеры
Ввод
3
5 2 1

Вывод
2
1 5
2 1


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: