Задана последовательность из n целых чисел d1, d2, ..., dn (d1 < d2 < ... < dn). Требуется построить такой неориентированный граф, что:
- в нем ровно dn + 1 вершин;
- в нем нет петель;
- в нем нет кратных ребер;
- в нем не более 106 ребер;
- его множество степеней равно d.
Вершины должны быть пронумерованы от 1 до (dn + 1).
Последовательностью степеней называется массив a длины, равной количеству вершин графа, такой, что ai — это количество вершин, смежных с i-й.
Множеством степеней называется отсортированная по возрастанию последовательность из всех различных значений из последовательности степеней.
Гарантируется, что существует такой граф, что все условия выполняются, и он содержит не более 106 ребер.
Выведите полученный граф.
Выходные данные
В первой строке выведите одно целое число m (1 ≤ m ≤ 106) — количество ребер в полученном графе. Гарантируется, что существует такой граф, что все условия выполняются, и он содержит не более 106 ребер.
В каждой из следующих m строк должны быть записаны два целых числа vi и ui (1 ≤ vi, ui ≤ dn + 1) — описание i-го ребра.