Задача №113622. Шахматы
Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске \(8 \times 8\) ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из \(n\) столбцов, \(i\)-й из которых содержит \(a_i\) клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.
Помогите Васе расставить на его доске минимальное число ладей требуемым образом
В первой строке входного файла задано целое число \(n\) — количество столбцов доски (\(1 \le n \le 1000\)). Следующая строка содержит \(n\) чисел \(a_1, a_2, \dots , a_n\) — количество клеток в столбцах (\(1 \le a_i \le 1000, a_1 \ge a_2 \ge \dots \ge a_n\)).
В первой строке выведите число \(k\) — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие \(k\) строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.
Если подходящих расстановок несколько, можно вывести любую.
Для приведенных входных данных возможна и следующая расстановка:
3 5 2 1
2 1 1 2 2