Залізниці Берляндії#8712

Залізниці Берляндії

1 секунда

128 мегабайтів

Складна

Уряд Берляндії вирішив побудувати в країні систему швидкісних залізниць. У Берляндії є $n$ міст, пронумерованих від $1$ до $n$ . Планується з'єднати деякі пари міст швидкісними залізницями. Кожна залізниця дозволяє переміщення в обох напрямках між містами, які вона з'єднує.

Майбутнє за швидкісними залізницями, тому важливо, щоб з будь-якого міста можна було дістатися до будь-якого іншого, використовуючи залізниці. Щоб зекономити кошти, вирішено побудувати мінімальну кількість доріг, необхідну для виконання цієї умови.

Уряд $i$ -го міста готовий обслуговувати рівно $d_{i}$ d_i поїздів, які курсуватимуть до інших міст. Тому кількість залізниць, що виходять з $i$ -го міста, повинна дорівнювати $d_{i}$ d_i. На щастя, виявилося, що $d_{1} + d_{2} + \dots + d_{n} = 2 n - 2$ d_1 + d_2 + \ldots + d_n = 2n - 2.

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

Вхідні дані

Перша строка містить ціле число $n$ - кількість міст у Берляндії ( $2 \leq n \leq 200000$ 2 \leq n \leq 200\,000). У наступному рядку знаходяться $n$ цілих чисел $d_{1}, d_{2}, \dots, d_{n}$ d_1, d_2, \ldots, d_n ( $1 \leq d_{i} < n$ 1 \leq d_i < n). Кількість міст, з'єднаних з $i$ -м містом залізницею, повинна збігатися з $d_{i}$ d_i для будь-якого міста $i$ . Гарантується, що $d_{1} + d_{2} + \dots + d_{n} = 2 n - 2$ d_1 + d_2 + \ldots + d_n = 2n - 2.

Вихідні дані

Потрібно вивести $n - 1$ n - 1 рядок - опис залізниць в оптимальному плані. Кожен рядок повинен містити два цілих числа $s_{i}$ s_i і $f_{i}$ f_i - номери міст, які потрібно з'єднати залізницею. Повинні виконуватися умови $1 \leq s_{i}, f_{i} \leq n$ 1 \leq s_i, f_i \leq n, $s_{i} \neq = f_{i}$ s_i \neq f_i.

Кількість міст, з'єднаних з $i$ -м містом залізницею, повинна збігатися з $d_{i}$ d_i для будь-якого міста $i$ . Максимальне число пересадок, яке потрібно, щоб дістатися з одного міста в інше, повинно бути якомога меншим. Якщо можливих оптимальних планів будівництва залізниць декілька, можна вивести будь-який з них. Гарантується, що існує план, який задовольняє всім умовам.

Приклади

Приклад 1

Приклад 2

Примітка

У першому тесті відповіддю є такий план:

Можна помітити, що з будь-якого міста можна дістатися до будь-якого іншого, використовуючи залізниці. Також кожне місто з'єднане залізницею з потрібною кількістю міст. Наприклад, місто $1$ з'єднане з трьома містами: $2$ , $4$ і $6$ ( $d_{1} = 3$ d_1 = 3).

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