Залізниці Берляндії
Уряд Берляндії вирішив побудувати в країні систему швидкісних залізниць. У Берляндії є 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. Побудувати план, в якому максимальне число пересадок менше, неможливо.