19775번 - Шахматы 스페셜 저지다국어

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске $8 \times 8$ ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму.

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

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

Помогите Васе расставить на его доске минимальное число ладей требуемым образом.Шахматы

В первой строке входного файла задано целое число $n$ --- количество столбцов доски ($1 \le n \le 1000$). Следущая строка содержит $n$ чисел $a_1, a_2, \ldots, a_n$ --- количество клеток в столбцах ($1 \le a_i \le 1000$, $a_1 \ge a_2 \ge \ldots \ge a_n$).

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

Если подходящих расстановок несколько, можно вывести любую.