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

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

Правительство i-го города готово обслуживать ровно di поездов, которые будут ходить в другие города. Поэтому количество железных дорог, выходящих из i-го города, должно быть равно di. К счастью, оказалось, что d1 + d2 + ... + dn = 2n - 2.

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

Входные данные

Первая строка содержит целое число n - количество городов в Берляндии (2 ≤ n ≤ 200 000). В следующей строке находится n целых чисел d1, d2, ..., dn (1 ≤ di < n). Количество городов, соединённых с i-м железной дорогой, должно совпадать с di для любого города i. Гарантируется, что d1 + d2 + ... + dn = 2n - 2.

Выходные данные

Требуется вывести n - 1 строк - описание железных дорог в оптимальном плане. Каждая строка должна содержать два целых числа si и fi - номера городов, которые нужно соединить железной дорогой. Должны выполняться условия 1 ≤ si, fi ≤ n, si ≠ fi.

Количество городов, соединённых с i-м городом железной дорогой, должно совпадать с di для любого города i. Максимальное число пересадок, которое требуется, чтобы добраться из одного города в другой, должно быть как можно меньше. Если возможных оптимальных планов строительства железных дорог несколько, можно вывести любой из них. Гарантируется, что существует план, удовлетворяющий всем условиям.

Пример

В первом тесте ответом является такой план:

Можно заметить, что из любого города можно добраться до любого другого, используя железные дороги. Также каждый город соединен железной дорогой с нужным количеством городов. Например, город 1 соединен с тремя городами: 2, 4 и 6 (d1 = 3).

Максимальное число пересадок, которое требуется сделать, чтобы доехать из одного города в другой, достигается, например, для городов 3 и 5, для этого нужно использовать 3 пересадки. Сначала надо доехать из города 3 в город 2, потом из города 2 в город 1, потом из города 1 в город 4 и, наконец, из города 4 в город 5. Построить план, в котором максимальное число пересадок меньше, невозможно.