Железные дороги Берляндии
Правительство Берляндии решило построить в стране систему скоростных железных дорог. В Берляндии n городов, пронумерованных натуральными числами от 1 до n. Планируется соединить скоростными железными дорогами некоторые пары городов. По каждой из дорог можно будет перемещаться в обоих направлениях между городами, которые она соединит.
За скоростными железными дорогами будущее, поэтому необходимо, чтобы, используя железные дороги, из любого города можно было добраться до любого другого. В целях экономии средств было решено построить минимальное число дорог, необходимое для выполнения этого условия.
Правительство i-го города готово обслуживать ровно d[i] поездов, которые будут ходить в другие города. Поэтому количество железных дорог, выходящих из i-го города, должно быть равно d[i]. К счастью, оказалось, что d[1] + d[2] + ... + d[n] = 2n - 2.
Правительство хочет, чтобы жители могли перемещаться между городами с как можно меньшим числом пересадок. Необходимо составить такой план системы железных дорог, чтобы максимальное число пересадок, которое необходимо сделать, чтобы добраться из одного города в другой, было как можно меньше.
Входные данные
Первая строка содержит целое число n - количество городов в Берляндии (2 ≤ n ≤ 200 000). В следующей строке находится n целых чисел d[1], d[2], ..., d[n] (1 ≤ d[i] < n). Количество городов, соединённых с i-м железной дорогой, должно совпадать с d[i] для любого города i. Гарантируется, что d[1] + d[2] + ... + d[n] = 2n - 2.
Выходные данные
Требуется вывести n - 1 строк - описание железных дорог в оптимальном плане. Каждая строка должна содержать два целых числа s[i] и f[i] - номера городов, которые нужно соединить железной дорогой. Должны выполняться условия 1 ≤ s[i], f[i] ≤ n, s[i] ≠ f[i].
Количество городов, соединённых с i-м городом железной дорогой, должно совпадать с d[i] для любого города i. Максимальное число пересадок, которое требуется, чтобы добраться из одного города в другой, должно быть как можно меньше. Если возможных оптимальных планов строительства железных дорог несколько, можно вывести любой из них. Гарантируется, что существует план, удовлетворяющий всем условиям.
Пример
В первом тесте ответом является такой план:
Можно заметить, что из любого города можно добраться до любого другого, используя железные дороги. Также каждый город соединен железной дорогой с нужным количеством городов. Например, город 1 соединен с тремя городами: 2, 4 и 6 (d[1] = 3).
Максимальное число пересадок, которое требуется сделать, чтобы доехать из одного города в другой, достигается, например, для городов 3 и 5, для этого нужно использовать 3 пересадки. Сначала надо доехать из города 3 в город 2, потом из города 2 в город 1, потом из города 1 в город 4 и, наконец, из города 4 в город 5. Построить план, в котором максимальное число пересадок меньше, невозможно.