베를란드 철도

베를란드 정부는 나라 안에 고속철도망을 짓기로 했다. 베를란드에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있다. 일부 도시 쌍은 고속철도로 연결된다. 열차 이용자는 각 철도를 양방향으로 이동할 수 있다.

고속열차는 교통의 미래이므로, 어떤 도시에서든 다른 어떤 도시로든 철도를 타고 갈 수 있어야 한다. 비용을 아끼기 위해 이 조건을 만족하는 철도 중 가장 적은 수만 짓기로 했다.

$i$번 도시의 정부는 정확히 $d_i$개의 열차를 운행하려고 한다. 즉 $i$번 도시와 다른 도시를 잇는 철도가 정확히 $d_i$개여야 한다. $d_1 + d_2 + \ldots + d_n = 2n - 2$임이 알려져 있다.

정부는 사람들이 열차를 갈아타는 횟수를 최대한 줄이기를 원한다. 한 도시에서 다른 도시로 갈 때 필요한 최대 환승 횟수가 가장 작아지도록 계획을 세워라.

첫 줄에 도시의 수 $n$이 주어진다 ($2 \leq n \leq 200000$). 다음 줄에는 $n$개의 정수 $d_1, d_2, \ldots, d_n$ ($1 \leq d_i < n$)이 주어진다. $i$번 도시는 정확히 $d_i$개의 다른 도시와 연결되어야 한다. $d_1 + d_2 + \ldots + d_n = 2n - 2$임이 보장된다.

최적 계획에 해당하는 철도를 $n-1$개의 줄에 출력한다. 각 줄에는 연결할 두 도시 $s_i$와 $f_i$를 출력한다 ($1 \leq s_i, f_i \leq n$, $s_i \neq f_i$). 모든 $i$에 대해 $i$번 도시에 연결된 철도의 수는 $d_i$와 같아야 한다. 임의의 두 도시 사이를 이동하는 데 필요한 최대 환승 횟수는 가능한 한 작아야 한다. 최적 계획이 여러 개라면 그중 아무거나 출력해도 된다. 조건을 만족하는 계획이 적어도 하나 존재함이 보장된다.

첫 번째 예제의 최적해는 다음과 같다.

1번 도시는 2번, 4번, 6번 도시와 연결되어 있다 ($d_1 = 3$). 환승이 3번 필요한 경우는 3번 도시와 5번 도시 사이다. 3번에서 2번 도시로, 2번에서 1번 도시로, 1번에서 4번 도시로, 마지막으로 4번에서 5번 도시로 이동한다. 모든 도시 쌍에 대해 이보다 적은 환승으로 가능한 계획은 없다.